QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641317#5704. Jokeratgc0 82ms9200kbC++231.4kb2024-10-14 19:51:222024-10-14 19:51:25

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 19:51:25]
  • 评测
  • 测评结果:0
  • 用时:82ms
  • 内存:9200kb
  • [2024-10-14 19:51:22]
  • 提交

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%