제출 #999784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999784		Mr_Husanboy	Joker (BOI20_joker)	C++17	0 / 100	0 ms	344 KiB

Joker

#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){
		//cout << a << ' ' << b << endl;
		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);
		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 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29