oj.uz

Submission #1043118

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

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 Runtime error 1 ms 760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -