oj.uz

Submission #999774

# Submission time Handle Problem Language Result Execution time Memory
999774 2024-06-16T06:40:56 Z Mr_Husanboy Joker (BOI20_joker) C++17
0 / 100
 1 ms 348 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> dis;
	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);
		dis.assign(n, 0);
		for(int i = 0; i < n; i ++){
			child[i] = {i};
		}
	}

	int get(int x){
		return (x == l[x] ? x : l[x] = get(l[x]));
	}

	void unite(int a, int b){
		int la = get(a), lb = get(b);
		if(la == lb){
			if((dis[a] + dis[b] + 1) % 2) odd = 1;
			return;
		}
		if(len(child[la]) > len(child[lb])) swap(la, lb), swap(a, b);
		int db = dis[b];
		b = lb, a = la;
		for(auto u : child[a]){
			child[b].push_back(u);
			dis[u] = db + 1;
		}
		l[a] = 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);

		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();
	}
}

Subtask #1
0 / 6.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

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