oj.uz

Submission #1043122

# Submission time Handle Problem Language Result Execution time Memory
1043122 2024-08-04T00:39:33 Z wood Joker (BOI20_joker) C++17
25 / 100
 1308 ms 5052 KB 
#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
	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);
		}
		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;
			}
		}
	}
	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

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 458 ms 3788 KB Output is correct
4 Correct 1308 ms 4976 KB Output is correct
5 Correct 330 ms 5052 KB Output is correct
6 Correct 153 ms 3816 KB Output is correct
7 Correct 165 ms 3776 KB Output is correct
8 Correct 278 ms 3528 KB Output is correct
9 Correct 339 ms 4040 KB Output is correct
10 Correct 791 ms 5016 KB Output is correct
11 Correct 522 ms 3688 KB Output is correct
12 Correct 686 ms 4832 KB Output is correct
13 Correct 274 ms 2760 KB Output is correct
14 Correct 271 ms 3268 KB Output is correct
15 Correct 634 ms 4532 KB Output is correct
16 Correct 773 ms 4980 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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