oj.uz

Submission #999802

# Submission time Handle Problem Language Result Execution time Memory
999802 2024-06-16T07:09:03 Z Mr_Husanboy Joker (BOI20_joker) C++17
0 / 100
 87 ms 23312 KB 
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
 
template<typename T>
int len(T &a){return a.size();}
 
 
struct DSU{
	vector<vector<int>> child;
	vector<int> l;
	vector<int> col;
	int n;
	bool odd = 0;
 
	DSU (int _n){init(_n);}
 
	void init(int _n){
		n = _n;
		child.resize(n);
		l.resize(n); iota(all(l), 0);
		col.assign(n, 0);
		for(int i = 0; i < n; i ++){
			child[i] = {i};
		}
	}
 
	void unite(int a, int b){
		if(l[a] == l[b]){
			if(col[a] == col[b]) odd = 1;
			return;
		}
		if(len(child[l[a]]) > len(child[l[b]])) swap(a, b);
		if(col[a] == col[b]){
			for(auto u : child[a]) col[u] ^= 1;
		}
		a = l[a], b = l[b];
		for(auto u : child[a]){
			child[b].push_back(u);
			l[u] = b;
		}
		child[a].clear();
	}
};
 
void solve(){
	int n, m, q; cin >> n >> m >> q;
	vector<pair<int,int>> edge(m);
	for(auto &[a, b] : edge) cin >> a >> b, a --, b --;
 
	vector<vector<pair<int,int>>> qu(m);
 
	for(int i = 0; i < q; i ++){
		int l, r; 
		cin >> l >> r;
		l --; r --;
		qu[l].push_back({r, i});
	}
	vector<int> ans(q);
	for(int i = 0; i < m; i ++){
		if(len(qu[i]) == 0) continue;
 
		DSU t(n);
		//cout << i << endl;
		for(int j = 0; j < i; j ++){
			//cout << edge[j].ff << endl;
			t.unite(edge[j].ff, edge[j].ss);
		}
		int r = m;
		if(t.odd == 0){
			r = i - 1;
			for(int j = m - 1; j >= i; j --){
				t.unite(edge[j].ff, edge[j].ss);
				if(t.odd){
					r = j;
					break;
				}
			}
		}
		for(auto [rig, j] : qu[i]){
			ans[j] = rig < r;
		}
	}
	for(auto u : ans){
		cout << (u ? "YES" : "NO") << '\n';
	}
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tests = 1;
	while(tests --){
		solve();
	}
	#ifdef LOCAL
	cout << "\nDone" << endl;
	#endif
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 58 ms 16512 KB Output is correct
4 Correct 87 ms 23312 KB Output is correct
5 Incorrect 58 ms 20168 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -