답안 #1043124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1043124	2024-08-04T00:42:31 Z	wood	Joker (BOI20_joker)	C++17	25 / 100	1347 ms	5052 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
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	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);
	}
	int result[200];
	for(int ii = 0; ii<200; ii++) {
		dsu D(n);
		for(int kk = 0; kk<min(ii,m); kk++) {
			if(D.get(e[kk].first)!=D.get(e[kk].second))
				D.merge(e[kk].first, e[kk].second);
			else if(D.side[e[kk].first]==D.side[e[kk].second]){
				result[ii] = INT_MAX;
				goto fail;
			}
		}
		for(int 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]){
				result[ii] = i;
				break;
			}
		}
		fail:
		continue;
	}
	for(int j = 0; j<q; j++){
		int l,b; cin>>l>>b;
		l--;
		if(b>result[l]) cout<<"NO\n";
		else cout<<"YES\n";
	}	
	return 0;
}

Subtask #1

0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	452 KB	Output is correct
7	Incorrect	1 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	452 KB	Output is correct
7	Incorrect	1 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	494 ms	3780 KB	Output is correct
4	Correct	1347 ms	5052 KB	Output is correct
5	Correct	331 ms	4872 KB	Output is correct
6	Correct	166 ms	3776 KB	Output is correct
7	Correct	156 ms	3780 KB	Output is correct
8	Correct	282 ms	3524 KB	Output is correct
9	Correct	331 ms	4036 KB	Output is correct
10	Correct	827 ms	4984 KB	Output is correct
11	Correct	538 ms	3780 KB	Output is correct
12	Correct	733 ms	4840 KB	Output is correct
13	Correct	238 ms	2760 KB	Output is correct
14	Correct	265 ms	3352 KB	Output is correct
15	Correct	648 ms	4536 KB	Output is correct
16	Correct	786 ms	4984 KB	Output is correct

Subtask #4

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	452 KB	Output is correct
7	Incorrect	1 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	452 KB	Output is correct
7	Incorrect	1 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #6

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	452 KB	Output is correct
7	Incorrect	1 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-