oj.uz

Submission #1043117

# Submission time Handle Problem Language Result Execution time Memory
1043117 2024-08-04T00:36:04 Z wood Joker (BOI20_joker) C++17
0 / 100
 2 ms 348 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<1; 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;
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen("/home/ioi/CLionProjects/ioi/input.txt ","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -