oj.uz

Submission #395401

# Submission time Handle Problem Language Result Execution time Memory
395401 2021-04-28T10:30:37 Z wenqi Joker (BOI20_joker) C++14
25 / 100
 2000 ms 17284 KB 
#include <bits/stdc++.h>

using namespace std;

int N, M, Q;

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

int ans[600069];

#define ROOT 20

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
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 Execution timed out 2090 ms 332 KB Time limit exceeded
8 Halted 0 ms 0 KB -

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 Execution timed out 2090 ms 332 KB Time limit exceeded
8 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 123 ms 15712 KB Output is correct
4 Correct 126 ms 17204 KB Output is correct
5 Correct 131 ms 16956 KB Output is correct
6 Correct 125 ms 15776 KB Output is correct
7 Correct 130 ms 15800 KB Output is correct
8 Correct 119 ms 15064 KB Output is correct
9 Correct 127 ms 15672 KB Output is correct
10 Correct 133 ms 17236 KB Output is correct
11 Correct 125 ms 15760 KB Output is correct
12 Correct 133 ms 16880 KB Output is correct
13 Correct 123 ms 14408 KB Output is correct
14 Correct 125 ms 15092 KB Output is correct
15 Correct 131 ms 16248 KB Output is correct
16 Correct 134 ms 17284 KB Output is correct

Subtask #4
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 Execution timed out 2090 ms 332 KB Time limit exceeded
8 Halted 0 ms 0 KB -

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 Execution timed out 2090 ms 332 KB Time limit exceeded
8 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 Execution timed out 2090 ms 332 KB Time limit exceeded
8 Halted 0 ms 0 KB -