답안 #280359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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