제출 #858956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858956		maks007	Joker (BOI20_joker)	C++14	0 / 100	0 ms	348 KiB

Joker

#include "bits/stdc++.h"

using namespace std;

signed main () {
	int n, m;
	cin >> n >> m;
	int q;
	cin >> q;
	vector <pair <int,int>> edge;
	set <int> g[n];
	vector <int> used(n, -1);
	int f = 0;
	function <void(int, int)> dfs=[&](int v, int color) {
		used[v] = color;
		for(auto i : g[v]) {
			if(used[i] == -1) dfs(i, 1-color);
			else {
				if(used[i] == used[v]) f = 1;
			}
		}
	};
	function <int(int)> check=[&](int x) {
		for(int i = x; i < m; i ++) {
			g[edge[i].first].insert(edge[i].second);
			g[edge[i].second].insert(edge[i].first);
		}
		f = 0;
		for(int i = 0; i < n; i ++) {
			if(used[i] == -1) dfs(i, 0);
		}
		for(auto &i : used) i = -1;
		for(int i = x; i < m; i ++) {
			g[edge[i].first].erase(edge[i].second);
			g[edge[i].second].erase(edge[i].first);
		}
		if(f) return 1;
		return 0;
	};
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v--;
		edge.push_back({u, v});
	}
	vector <int> GG(201, 0);
	for(int i = 0; i < min(m, 200); i ++) {
		if(i) {
			g[edge[i-1].first].insert(edge[i-1].second);
			g[edge[i-1].second].insert(edge[i-1].first);
		}
		int l = i + 1, r = m-1;
		while(l < r) {
			int mid = (l + r + 1) / 2;
			// cout << mid << " ";
			if(check(mid)) l = mid;
			else r = mid - 1; 
		}
		GG[i] = l;
		// cout << i + 1 << " -> " << l + 1 << "\n";
	}

	// cout << gg + 1 << "\n";
	while(q --) {
		int l, r;
		cin >> l >> r;
		l --, r --;
		if(l <= 200) {
			int gg = GG[l]; 
			if(r < gg) cout << "YES\n";
			else cout << "NO\n";
		}
	}
	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29