Submission #999799

#	Time	Username	Problem	Language	Result	Execution time	Memory
999799		Mr_Husanboy	Mixture (BOI20_mixture)	C++17	0 / 100	1 ms	348 KiB

Mixture

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

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40