Submission #289906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
289906	2020-09-03T08:19:36 Z	someone_aa	Joker (BOI20_joker)	C++17	25 / 100	1503 ms	17912 KB

Joker

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 200100;
ll n, m, q;

vector<pii>g[maxn];

bool visited[maxn];
int color[maxn];

bool check(int l, int r) {
	memset(visited, false,sizeof(visited));
	memset(color, 0, sizeof(color));

	bool cycle = false;

	for(int i=1;i<=n;i++) {
		if(!visited[i]) {
			visited[i] = true;
			color[i] = 1;

			queue<int>q;
			q.push(i);

			while(!q.empty()) {
				int curr = q.front();
				q.pop();

				for(auto i:g[curr]) {
					if(l <= i.second && i.second <= r) continue;

					if(!visited[i.first]) {
						visited[i.first] = true;
						color[i.first] = 3 - color[curr];
						q.push(i.first);
					}
					else {
						if(color[i.first] == color[curr]) cycle = true;
					}
				}
			}
		}
	}

	return cycle;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m>>q;

	int u, v;
	for(int i=1;i<=m;i++) {
		cin>>u>>v;
		g[u].pb(mp(v, i));
		g[v].pb(mp(u, i));
	}

	if(!check(1, 1)) {
		for(int i=0;i<q;i++) {
			cout<<"NO\n";
		}
		return 0;
	}
	
	int rmost = 1;
	for(ll cekor=m/2;cekor>0;cekor/=2) {
		while(rmost + cekor <= m && check(1, rmost+cekor)) rmost += cekor;
	}


	int l, r;
	while(q--) {
		cin>>l>>r;

		if(r <= rmost) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6016 KB	Output is correct
2	Correct	4 ms	6016 KB	Output is correct
3	Correct	253 ms	11512 KB	Output is correct
4	Correct	140 ms	13816 KB	Output is correct
5	Correct	1503 ms	13948 KB	Output is correct
6	Correct	392 ms	17144 KB	Output is correct
7	Correct	419 ms	17256 KB	Output is correct
8	Correct	377 ms	16052 KB	Output is correct
9	Correct	611 ms	16460 KB	Output is correct
10	Correct	1420 ms	17528 KB	Output is correct
11	Correct	620 ms	16912 KB	Output is correct
12	Correct	1299 ms	17648 KB	Output is correct
13	Correct	213 ms	15992 KB	Output is correct
14	Correct	384 ms	16564 KB	Output is correct
15	Correct	1047 ms	17396 KB	Output is correct
16	Correct	1458 ms	17912 KB	Output is correct