Submission #388827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
388827	2021-04-13T05:47:18 Z	huangqr	Joker (BOI20_joker)	C++14	25 / 100	131 ms	21820 KB

Joker

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
const ll lim=2e5+5;
ll par[lim],rnk[lim],rel[lim];
ll parcpy[lim],rnkcpy[lim];
//rnk[findset(x)]-rnk[x]

pl findset(ll par[],ll x){
	ll cur=0,og=x;
	while(x!=par[x]){
		if(rel[x])cur=1-cur;
		x=par[x];
	}
	par[og]=x;
	rel[og]=cur;
	return {x,cur};
}

void mergeset(ll par[],ll rnk[],ll x,ll y){
	pl px=findset(par,x),py=findset(par,y);
	x=px.first,y=py.first;
	if(x==y)return;
	if(rnk[x]>rnk[y])swap(x,y);
	if(rnk[x]==rnk[y])rnk[y]++;
	par[x]=y;
	rnk[y]++;
	rel[x]=(px.second==py.second);
	return;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL);
	ll n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)par[i]=i;
	vector<pl>v;
	vector<pl>qs[lim];
	for(int i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		v.emplace_back(a,b);
	}	
	bool ans[lim],cfa=0;
	fill(ans,ans+lim,0);
	for(int i=0;i<q;i++){
		ll a,b;
		cin>>a>>b;
		b--,b++;//b is the minimum index that can be used on the right side
		qs[b].emplace_back(a,i);
	}
	for(auto x:qs[m])ans[x.second]=cfa;//,cout<<"proced0:"<<x.second<<"\n";
	for(int i=m-1;i>=1;i--){
		sort(qs[i].begin(),qs[i].end());
		pl x=findset(par,v[i].first),y=findset(par,v[i].second);
		if(x.first==y.first){
			if(x.second==y.second){
				cfa=1;
			}
		}
		else mergeset(par,rnk,v[i].first,v[i].second);
		pl resx=findset(par,v[i].first),resy=findset(par,v[i].second);
		if(qs[i].empty())continue;
		for(auto x:qs[i])ans[x.second]=cfa;//cout<<"proced:"<<x.second<<"\n";
	}
	for(int i=0;i<q;i++){
		if(ans[i])cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:64:6: warning: variable 'resx' set but not used [-Wunused-but-set-variable]
   64 |   pl resx=findset(par,v[i].first),resy=findset(par,v[i].second);
      |      ^~~~
Joker.cpp:64:35: warning: variable 'resy' set but not used [-Wunused-but-set-variable]
   64 |   pl resx=findset(par,v[i].first),resy=findset(par,v[i].second);
      |                                   ^~~~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Incorrect	4 ms	5160 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Incorrect	4 ms	5160 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Correct	114 ms	16380 KB	Output is correct
4	Correct	122 ms	21228 KB	Output is correct
5	Correct	127 ms	21584 KB	Output is correct
6	Correct	128 ms	19360 KB	Output is correct
7	Correct	119 ms	19340 KB	Output is correct
8	Correct	105 ms	17968 KB	Output is correct
9	Correct	112 ms	18900 KB	Output is correct
10	Correct	123 ms	21532 KB	Output is correct
11	Correct	131 ms	19388 KB	Output is correct
12	Correct	125 ms	21420 KB	Output is correct
13	Correct	109 ms	17400 KB	Output is correct
14	Correct	111 ms	18492 KB	Output is correct
15	Correct	123 ms	20404 KB	Output is correct
16	Correct	129 ms	21820 KB	Output is correct