oj.uz

Submission #858962

# Submission time Handle Problem Language Result Execution time Memory
858962 2023-10-09T13:15:06 Z maks007 Joker (BOI20_joker) C++14
0 / 100
 0 ms 348 KB 
#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);
			f = 0;
			for(int j = 0; j < n; j ++) {
				if(used[j] == -1) dfs(j, 0);
			}
			for(auto &j:used)j=-1;
			if(f) {
				// cout << i + 1 << " < - \n";
				GG[i] = i;
				continue;
			}
		}
		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;
	}

	// for(int i = 0; i < min((int)GG.size(), m); i ++) {
	// 	cout << i + 1 << " " << GG[i] + 1 << "\n";
	// }

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

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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