Submission #858950

#	Time	Username	Problem	Language	Result	Execution time	Memory
858950		maks007	Joker (BOI20_joker)	C++14	25 / 100	538 ms	19136 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;
	vector <vector <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].push_back(edge[i].second);
			g[edge[i].second].push_back(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(auto &i : g) i.clear();
		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});
	}
	int l = 0, r = m-1;
	while(l < r) {
		int mid = (l + r + 1) / 2;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	int gg = l;
	// cout << gg + 1 << "\n";
	while(q --) {
		// int l, r;
		cin >> l >> r;
		l --, r --;
		if(l == 0) {
			if(r < gg) cout << "YES\n";
			else cout << "NO\n";
		}
	}
	return 0;
}

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