社区讨论
本机正常CF上TLE
CF1139E Maximize Mex参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo7po3z2
- 此快照首次捕获于
- 2023/10/27 05:43 2 年前
- 此快照最后确认于
- 2023/10/27 05:43 2 年前
如题所述
这份代码本机上跑几组样例都对了
但是CF上TLE了……
CPP#include <iostream>
const int N = 5005;
struct EDGE {
int t, next;
EDGE (const int& _t = 0,const int& _n = 0)
: t(_t), next(_n) {}
} edge[N<<1];
int head[N<<1], edge_tot = 1;
void add_edge(int f,int t) {
edge[head[f] = ++edge_tot] = EDGE(t,head[f]);
}
int ans[N], id[N];
int ptt[N], blg[N];
bool baned[N];
int stamp[N], refer[N];
int n, m, d;
bool match(int u,int time) {
for(int i = head[u], v;i;i = edge[i].next) {
if(baned[i>>1])
continue;
v = edge[i].t;
if(stamp[v] == time)
continue;
stamp[v] = time;
if(!refer[v]||match(refer[v],time)) {
refer[v] = u;
return true;
}
}
return false;
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)
scanf("%d",&ptt[i]);
for(int i = 1;i <= n;++i)
scanf("%d",&blg[i]);
for(int i = 1;i <= n;++i) {
add_edge(ptt[i],blg[i]+N);
add_edge(blg[i]+N,ptt[i]);
}
scanf("%d",&d);
for(int i = 1;i <= d;++i) {
scanf("%d",&id[i]);
baned[id[i]] = true;
}
int time_cnt = 1;
for(int i = d;i >= 1;--i, ++time_cnt) {
for(ans[i] = ans[i+1];match(ans[i],time_cnt);++ans[i], ++time_cnt);
baned[id[i]] = false;
}
for(int i = 1;i <= d;++i)
printf("%d\n",ans[i]);
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...