oj.uz

Submission #395405

# Submission time Handle Problem Language Result Execution time Memory
395405 2021-04-28T10:32:12 Z wenqi Joker (BOI20_joker) C++14
41 / 100
 1585 ms 18200 KB 
#include <bits/stdc++.h>

using namespace std;

int N, M, Q;

int parents[600069];
int sz[600069];

int ans[600069];

#define ROOT 300

struct E {
	int i, a;
	int j, b;
};

struct R {
	int i, l, r, bl;
};

vector<E> moves;

void reset() {
	for (int i = 0; i < 2 * N; i++) {
		parents[i] = i;
		sz[i] = 1;
	}
	moves.clear();
}

int getp(int i) {
	return i == parents[i] ? i : getp(parents[i]);
}

bool join(int a, int b) {
	a = getp(a);
	b = getp(b);

	if(a == b) {
		moves.push_back({-1});
		return false;
	}

	if(sz[a] > sz[b]) {
		moves.push_back({b, parents[b], a, sz[a]});
		parents[b] = a;
		sz[a] += sz[b];
	}else{
		moves.push_back({a, parents[a], b, sz[b]});
		parents[a] = b;
		sz[b] += sz[a];
	}

	return getp(a) == getp((a + N) % (2 * N)) or getp(b) == getp((b + N) % (2 * N));
}

void reload() {
	auto p = moves.back();
	moves.pop_back();

	if(p.i == -1)
		return;

	parents[p.i] = p.a;
	sz[p.j] = p.b;
}

int A[200069];
int B[200069];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		A[i] = --a;
		B[i] = --b;
	}
	vector<R> queries;
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		queries.push_back({i, l, r, l / ROOT});
	}
	sort(queries.begin(), queries.end(), [](R& a, R& b) {
		return a.bl < b.bl or (a.bl == b.bl and a.r > b.r);
	});
	bool made = false;
	int pbl = -1;
	int nxt = 0;
	int up = 0;
	int start = 1;
	bool doable = false;
	reset();
	for (const R& a : queries) {
		int Bs = a.bl * ROOT;

		if(a.bl != pbl) {
			doable = false;

			for(int i = 0; i < up; i++) {
				reload();
			}

			for (; start < Bs; start++) {
				made |= join(A[start], B[start] + N);
				made |= join(A[start] + N, B[start]);
			}

			nxt = M;
			pbl = a.bl;
		}

		for(; nxt > a.r; nxt--) {
			doable |= join(A[nxt], B[nxt] + N);
			doable |= join(A[nxt] + N, B[nxt]);
			up += 2;
		}

		bool k = false;

		int cnt = 0;

		for (int i = Bs; i < a.l; i++) {
			if(i == 0) continue;
			k |= join(A[i], B[i] + N);
			k |= join(A[i] + N, B[i]);
			cnt += 2;
		}

		ans[a.i] = made or k or doable;

		for (int i = 0; i < cnt; i++) {
			reload();
		}
	}
	for(int i = 0; i < Q; i++) {
		cout << (ans[i] ? "YES" : "NO") << '\n';
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Runtime error 13 ms 844 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 120 ms 15644 KB Output is correct
4 Correct 155 ms 17260 KB Output is correct
5 Correct 129 ms 16912 KB Output is correct
6 Correct 134 ms 15632 KB Output is correct
7 Correct 125 ms 15740 KB Output is correct
8 Correct 123 ms 15068 KB Output is correct
9 Correct 147 ms 15660 KB Output is correct
10 Correct 168 ms 17204 KB Output is correct
11 Correct 134 ms 15652 KB Output is correct
12 Correct 157 ms 16940 KB Output is correct
13 Correct 127 ms 14416 KB Output is correct
14 Correct 135 ms 15084 KB Output is correct
15 Correct 133 ms 16344 KB Output is correct
16 Correct 154 ms 17276 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 120 ms 15644 KB Output is correct
30 Correct 155 ms 17260 KB Output is correct
31 Correct 129 ms 16912 KB Output is correct
32 Correct 134 ms 15632 KB Output is correct
33 Correct 125 ms 15740 KB Output is correct
34 Correct 123 ms 15068 KB Output is correct
35 Correct 147 ms 15660 KB Output is correct
36 Correct 168 ms 17204 KB Output is correct
37 Correct 134 ms 15652 KB Output is correct
38 Correct 157 ms 16940 KB Output is correct
39 Correct 127 ms 14416 KB Output is correct
40 Correct 135 ms 15084 KB Output is correct
41 Correct 133 ms 16344 KB Output is correct
42 Correct 154 ms 17276 KB Output is correct
43 Correct 1217 ms 16376 KB Output is correct
44 Correct 1221 ms 18040 KB Output is correct
45 Correct 1191 ms 17964 KB Output is correct
46 Correct 1212 ms 16424 KB Output is correct
47 Correct 1412 ms 16584 KB Output is correct
48 Correct 1345 ms 16564 KB Output is correct
49 Correct 1403 ms 18200 KB Output is correct
50 Correct 1151 ms 16252 KB Output is correct
51 Correct 1244 ms 17052 KB Output is correct
52 Correct 1297 ms 18100 KB Output is correct
53 Correct 1106 ms 15340 KB Output is correct
54 Correct 1517 ms 16204 KB Output is correct
55 Correct 1585 ms 17112 KB Output is correct
56 Correct 1566 ms 17996 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Runtime error 13 ms 844 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Runtime error 13 ms 844 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -