Submission #858950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858950	2023-10-09T12:46:41 Z	maks007	Joker (BOI20_joker)	C++14	25 / 100	538 ms	19136 KB

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.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	482 ms	16652 KB	Output is correct
4	Correct	538 ms	19136 KB	Output is correct
5	Correct	463 ms	14500 KB	Output is correct
6	Correct	513 ms	14704 KB	Output is correct
7	Correct	474 ms	14736 KB	Output is correct
8	Correct	457 ms	12448 KB	Output is correct
9	Correct	527 ms	15276 KB	Output is correct
10	Correct	523 ms	16992 KB	Output is correct
11	Correct	487 ms	13940 KB	Output is correct
12	Correct	512 ms	16152 KB	Output is correct
13	Correct	427 ms	9156 KB	Output is correct
14	Correct	477 ms	12484 KB	Output is correct
15	Correct	502 ms	16064 KB	Output is correct
16	Correct	532 ms	17108 KB	Output is correct