QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210766 | #4000. Dynamic Reachability | Cirno_9 | TL | 0ms | 19336kb | C++17 | 3.5kb | 2023-10-11 19:53:09 | 2023-10-11 19:53:09 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define pbk push_back
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(int i=a,i##i=b;i>=i##i;--i)
#define cl(a,x) memset(a,x,sizeof a)
using namespace std;
typedef long long ll;
namespace Cirno_loves_Reimu{
char buf[1<<20],obuf[1<<20],*p1,*p2,*p3=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline int read(){
int x=0;bool f=0;
char c=getchar();
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=1,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
return f?-x:x;
}
void write(ll x){
if(x<0)putchar('-'),x=-x;
static char buf[15];
static int len=-1;
do buf[++len]=x%10+48,x/=10;while(x);
while(len>=0)putchar(buf[len]),--len;
putchar('\n');
}
void flush(){
fwrite(obuf,p3-obuf,1,stdout),exit(0);
}
#undef getchar
#undef putchar
}using namespace Cirno_loves_Reimu;
const int N=1e5+7,B=3,L=2*B;
int n,m,q,u[N],v[N],id[N],p[N],del[N],us[N],C;
int o[N],x[N],y[N],k[N],d[N];
vector<int>e[N],S[N],a[N],w[N];
bitset<L>f[N],g[L];
inline void add(int x){if(!~id[x])id[x]=C,p[C]=x,C++;}
int low[N],dfn[N],st[N],pd[N],tot,cnt,bel[N],hd;
void tarjan(int x){
st[++hd]=x,pd[x]=1,dfn[x]=low[x]=++cnt;
for(int k:e[x])if(!us[k]&&!del[k]){
int to=v[k];
if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]);
else if(pd[to])low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x]){
++tot;
while(st[hd+1]!=x)bel[st[hd]]=tot,pd[st[hd--]]=0;
}
}
int Q[N],tl;
void bfs(){
tl=1,hd=0;
FOR(i,1,tot)if(!d[i])Q[++hd]=i;
while(hd>=tl){
int x=Q[tl++];
for(int to:a[x])if(!--d[to])Q[++hd]=to;
}
ROF(i,hd,1){
int x=Q[i];
for(int to:a[x])f[x]|=f[to];
}
FOR(i,0,C-1)g[i]=f[bel[p[i]]];
}
void chk(int x,int y){
if(x==y){
puts("YES");
return;
}
bitset<L>q,vs;
vs.set(),q.set(x);
while(1){
auto h=q&vs;
if(h.none())break;
int X=h._Find_first();
vs.reset(X),q|=g[X];
for(int k:w[X])if(!del[k])q.set(id[v[k]]);
if(q[y]){
puts("YES");
return;
}
}
puts("NO");
}
void work(int l,int r){
// cerr<<"["<<l<<','<<r<<"]"<<endl;
C=0,cl(id,-1),cl(us,0);
FOR(i,l,r)if(o[i]==1){
int X=u[k[i]],Y=v[k[i]];
add(X),add(Y),us[k[i]]=1,w[id[X]].pbk(k[i]);
}
else add(x[i]),add(y[i]);
hd=cnt=tot=0;
cl(dfn,0),cl(low,0),cl(pd,0),cl(d,0),cl(st,0),cl(bel,0);
FOR(i,1,n)if(!dfn[i])tarjan(i);
FOR(i,1,tot)S[i].clear(),a[i].clear();
FOR(i,1,n)S[bel[i]].pbk(i);
FOR(i,1,tot){
f[i].reset();
for(int x:S[i])if(~id[x])f[i].set(id[x]);
}
FOR(i,1,m)if(!del[i]&&!us[i]){
int X=bel[u[i]],Y=bel[v[i]];
if(X!=Y)a[X].pbk(Y),++d[Y];
}
bfs();
FOR(i,l,r)if(o[i]==1)del[k[i]]^=1;
else chk(id[x[i]],id[y[i]]);
FOR(i,0,C-1)w[i].clear();
}
signed main(){
n=read(),m=read(),q=read();
FOR(i,1,m)u[i]=read(),v[i]=read(),e[u[i]].pbk(i);
FOR(i,1,q){
o[i]=read();
if(o[i]==1)k[i]=read();
else x[i]=read(),y[i]=read();
}
for(int i=1;i<=q;i+=B)work(i,min(i+B-1,q));
flush();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 19336kb
input:
5 6 7 1 2 1 3 2 4 3 4 3 5 4 5 2 1 5 2 2 3 1 3 1 4 2 1 4 1 3 2 1 5
output:
YES NO NO YES
result:
ok 4 lines
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 100000 36671 44121 25592 44321 13226 46463 13060 25694 14021 20087 22881 38333 34655 47774 22868 26462 31154 48710 27491 32365 5874 47497 17622 28600 1886 14193 22315 23656 14973 22704 1335 25384 22612 34915 2852 48213 23334 25519 24342 28784 6238 36125 14598 39494 33069 34250 2123 3059...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...