QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641317 | #5704. Joker | atgc | 0 | 82ms | 9200kb | C++23 | 1.4kb | 2024-10-14 19:51:22 | 2024-10-14 19:51:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,m,Q;
struct{int u,v;}e[maxn];
int fa[maxn<<1];struct{int sz,u;}ver[maxn];int vtp;
int gfa(int x){for(;fa[x]>0;x=fa[x]);return x;}
bool mer(int u,int v){u=gfa(u),v=gfa(v);
return u==v?0:(fa[u]>fa[v]&&(swap(u,v),1),ver[++vtp]={fa[v],v},fa[u]+=fa[v],fa[v]=u);}
void roll(){
auto[fav,v]=ver[vtp--];
fa[fa[v]]-=fav,fa[v]=fav;
}
bool psh(int i){
auto[u,v]=e[i];
int _u=gfa(u+n),_v=gfa(v+n);
if(_u==_v)return 0;
u=gfa(u),v=gfa(v);
mer(u,_v),mer(_u,v);
return 1;
}
int R[maxn];//最大的R,使得[l,r]joker win
void sol(int ql,int qr,int l,int r){//added all edge in [1,ql-1] and [r+1,m]
// infun(ql,qr,l,r);
if(l==r||ql>qr)return fill(R+ql,R+qr+1,l);
int md=(ql+qr)>>1;
int cv=vtp;
for(int nw=ql;nw<md;++nw){
if(!psh(nw)){
while(vtp!=cv)roll();
fill(R+md,R+qr+1,m);
sol(ql,md-1,l,r);
return;
// R[md]=m+1;break;
}
}
int cvmd=vtp;
int p=r;
for(;p>=l;--p){
if(!p || !psh(p))break;
}
R[md]=p;
while(vtp!=cvmd)roll();
sol(md+1,qr,p,r);
while(vtp!=cv)roll();
for(int q=r;q>p;--q)psh(q);
sol(ql,md-1,l,p);
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>Q;
for(int i=1;i<=m;++i)cin>>e[i].u>>e[i].v;
memset(fa,-1,sizeof fa);
sol(1,m,0,m);
while(Q--){
int l,r;cin>>l>>r;
if(R[l]<=r)cout<<"NO\n";
else cout<<"YES\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 6864kb
input:
6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 4 8 4 7
output:
NO YES
result:
ok 2 lines
Test #2:
score: 6
Accepted
time: 2ms
memory: 7696kb
input:
2 1 1 1 2 1 1
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Wrong Answer
time: 2ms
memory: 7696kb
input:
4 6 6 4 3 1 4 1 3 2 1 3 2 2 4 3 3 6 6 4 5 3 4 1 2 5 6
output:
YES NO NO YES YES NO
result:
wrong answer 2nd lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #55:
score: 25
Accepted
time: 82ms
memory: 9200kb
input:
100000 199997 200000 79109 44896 79109 66117 66117 91800 91800 24387 24387 74514 48558 74514 48558 37561 37561 76920 79598 76920 79598 69196 69196 79004 49065 79004 70038 49065 15497 70038 15497 67507 25073 67507 25073 41762 41762 71848 71848 32073 32073 43754 72852 43754 41209 72852 68112 41209 629...
output:
NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO YES ...
result:
ok 200000 lines
Test #56:
score: 0
Wrong Answer
time: 50ms
memory: 9132kb
input:
200000 200000 200000 156700 169748 169748 15408 158166 15408 117779 158166 2384 169748 4408 156700 117779 33510 90442 4408 4408 162134 117779 171528 90442 38746 33510 152759 171528 184558 162134 8761 154354 171528 23832 171528 23832 68341 98972 152759 80275 98972 98972 67486 67486 31710 31710 127052...
output:
YES YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES NO...
result:
wrong answer 1st lines differ - expected: 'NO', found: 'YES'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%