Submission #1043119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043119	2024-08-04T00:37:56 Z	wood	Joker (BOI20_joker)	C++17	25 / 100	318 ms	9660 KB

Joker

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
 
struct dsu{
	vector<bool> side;
	vector<int> rep, size;
	dsu(int n){
		for(int i = 0; i<n; i++){
			rep.pb(i);
			side.pb(0);
			size.pb(1);
		}
	}
	int get(int u){
		if(u == rep[u]) return u;
		int oldparent = rep[u];
		rep[u] = get(rep[u]);
		side[u] = side[u]^side[oldparent];
		return rep[u];
	}
	void merge(int u, int v){
		int oldu = u, oldv = v;
		u = get(u); v = get(v);
		if(size[v]>size[u]){
		       	swap(u,v);
			swap(oldu, oldv);
		 }
		side[v] = !(side[oldv]^side[oldu]);
		size[u]+=size[v];
		rep[v] = u;
	}
};
 
int main() {
#ifndef ONLINE_JUDGE
	//freopen("/home/ioi/CLionProjects/ioi/input.txt ","r",stdin);
#endif
	int n,m,q; cin>>n>>m>>q;
	vector<pair<int,int>> e;
	for(int i = 0; i<m; i++){
		int a,b; cin>>a>>b;
		a--; b--;
		e.emplace_back(a,b);
	}
	dsu D(n);
	vector<int> r;
	int i;
	for(i = m-1; i>=0; i--) {
		int l = e[i].first, r = e[i].second;
		if(D.get(l)!=D.get(r))
			D.merge(l,r);
		else if(D.side[l]==D.side[r])
			break;
	}
	for(int j = 0; j<q; j++){
		int l,b; cin>>l>>b;
		if(b>i) cout<<"NO\n";
		else cout<<"YES\n";
	}	
	return 0;
}

Subtask #1
0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	277 ms	7872 KB	Output is correct
4	Correct	277 ms	8892 KB	Output is correct
5	Correct	313 ms	9512 KB	Output is correct
6	Correct	318 ms	7868 KB	Output is correct
7	Correct	274 ms	7868 KB	Output is correct
8	Correct	285 ms	6844 KB	Output is correct
9	Correct	268 ms	7360 KB	Output is correct
10	Correct	316 ms	9128 KB	Output is correct
11	Correct	275 ms	7612 KB	Output is correct
12	Correct	300 ms	9304 KB	Output is correct
13	Correct	295 ms	6612 KB	Output is correct
14	Correct	292 ms	7356 KB	Output is correct
15	Correct	279 ms	8896 KB	Output is correct
16	Correct	282 ms	9660 KB	Output is correct