Submission #280359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
280359	2020-08-22T16:45:36 Z	spdskatr	Joker (BOI20_joker)	C++14	25 / 100	522 ms	19448 KB

Joker

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

int N, M, Q, seen[200005], col[200005];
vector<pii> graph[200005];

int dfs(int x, int l) {
	seen[x] = 1;
	for (pii p : graph[x]) {
		int v = p.fi, e = p.se;
		if (e >= l) {
			if (seen[v]) {
				if (col[v] == col[x]) return 1;
			} else {
				col[v] = !col[x];
				if (dfs(v, l)) return 1;
			}
		}
	}
	return 0;
}
int decide(int l) {
	for (int i = 1; i <= N; i++) if (!seen[i]) if (dfs(i, l)) return 1;
	return 0;
}

int main() {
	scanf("%d %d %d", &N, &M, &Q);
	for (int i = 1; i <= M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back({ b, i });
		graph[b].push_back({ a, i });
	}
	int lo = 0, hi = M;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		memset(seen, 0, sizeof(seen));
		memset(col, 0, sizeof(col));
		if (decide(mid)) lo = mid;
		else hi = mid;
	}
	for (int q = 0; q < Q; q++) {
		int l, r;
		scanf("%d %d", &l, &r);
		assert(l == 1);
		if (r+1 >= hi) printf("NO\n");
		else printf("YES\n");
	}
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
Joker.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	4 ms	6528 KB	Output is correct
3	Runtime error	12 ms	13056 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	4 ms	6528 KB	Output is correct
3	Runtime error	12 ms	13056 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	4 ms	6528 KB	Output is correct
3	Correct	278 ms	15096 KB	Output is correct
4	Correct	522 ms	19448 KB	Output is correct
5	Correct	240 ms	18808 KB	Output is correct
6	Correct	400 ms	18428 KB	Output is correct
7	Correct	451 ms	17656 KB	Output is correct
8	Correct	359 ms	17912 KB	Output is correct
9	Correct	485 ms	18296 KB	Output is correct
10	Correct	395 ms	18040 KB	Output is correct
11	Correct	256 ms	17440 KB	Output is correct
12	Correct	334 ms	18028 KB	Output is correct
13	Correct	240 ms	17276 KB	Output is correct
14	Correct	374 ms	18680 KB	Output is correct
15	Correct	310 ms	18424 KB	Output is correct
16	Correct	367 ms	18424 KB	Output is correct