oj.uz

Submission #1082344

# Submission time Handle Problem Language Result Execution time Memory
1082344 2024-08-31T07:52:28 Z vuavisao Experimental Charges (NOI19_charges) C++14
100 / 100
 29 ms 8796 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;
const char STATE[] = {'A', 'R', '?'};

struct dsu {
	int n = 0;
	vector<int> parent = {};
	
	void resize(int _n) {
		n = _n; 
		parent.resize(n + 10); for (int i = 1; i <= n; ++ i) parent[i] = i;
	}
	dsu() {};
	dsu(int _n) { this->resize(_n); };

	int ancestor(int u) {
		if (parent[u] == u) return u;
		return parent[u] = ancestor(parent[u]);
	}

	bool join(int u, int v) {
		u = ancestor(u); v = ancestor(v);
		if (u == v) return false;
		parent[v] = u;
		return true;
	}
};

int n, q;
int type[N];
vector<pair<int, int>> g[N];
pair<int, int> qq[N];

int state[N];
int res[N];

void dfs(int u) {
	for (const auto& x : g[u]) {
		int v = x.first, change = x.second;
		if (state[v] != -1) continue;
		state[v] = state[u] ^ change;
		dfs(v);
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n >> q;
	for (int i = 1; i <= q; ++ i) {
		char c; cin >> c;
		cin >> qq[i].first >> qq[i].second;
		int u = qq[i].first, v = qq[i].second;
		if (c == 'A') {
			g[u].push_back(make_pair(v, 1));
			g[v].push_back(make_pair(u, 1));
		}
		else if (c == 'R') {
			g[u].push_back(make_pair(v, 0));
			g[v].push_back(make_pair(u, 0));
		}
		else {
			type[i] = 1;
		}
	}

	memset(state, -1, sizeof(state));
	for (int i = 1; i <= n; ++ i) {
		if (state[i] == -1) {
			state[i] = 0;
			dfs(i);
		}
	}
	dsu dsu(n);
	for (int i = 1; i <= q; ++ i) {
		int u = qq[i].first, v = qq[i].second;
		if (type[i] == 0) {
			dsu.join(u, v);
		}
		else {
			int res = 2;
			if (dsu.ancestor(u) == dsu.ancestor(v)) {
				res = (state[u] == state[v]);
			}
			cout << STATE[res] << '\n';
		}
	}
	return (0 ^ 0);
}

/// Code by vuavisao

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 2 ms 3160 KB Output is correct
5 Correct 2 ms 3160 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7636 KB Output is correct
2 Correct 21 ms 7892 KB Output is correct
3 Correct 20 ms 7120 KB Output is correct
4 Correct 24 ms 7856 KB Output is correct
5 Correct 22 ms 7892 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8796 KB Output is correct
2 Correct 28 ms 8272 KB Output is correct
3 Correct 26 ms 7676 KB Output is correct
4 Correct 28 ms 8788 KB Output is correct
5 Correct 26 ms 8276 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8540 KB Output is correct
2 Correct 28 ms 8024 KB Output is correct
3 Correct 27 ms 8020 KB Output is correct
4 Correct 28 ms 8272 KB Output is correct
5 Correct 26 ms 8284 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 2 ms 3160 KB Output is correct
5 Correct 2 ms 3160 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 2 ms 3084 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 2 ms 3160 KB Output is correct
5 Correct 2 ms 3160 KB Output is correct
6 Correct 17 ms 7636 KB Output is correct
7 Correct 21 ms 7892 KB Output is correct
8 Correct 20 ms 7120 KB Output is correct
9 Correct 24 ms 7856 KB Output is correct
10 Correct 22 ms 7892 KB Output is correct
11 Correct 20 ms 8796 KB Output is correct
12 Correct 28 ms 8272 KB Output is correct
13 Correct 26 ms 7676 KB Output is correct
14 Correct 28 ms 8788 KB Output is correct
15 Correct 26 ms 8276 KB Output is correct
16 Correct 18 ms 8540 KB Output is correct
17 Correct 28 ms 8024 KB Output is correct
18 Correct 27 ms 8020 KB Output is correct
19 Correct 28 ms 8272 KB Output is correct
20 Correct 26 ms 8284 KB Output is correct
21 Correct 1 ms 3164 KB Output is correct
22 Correct 1 ms 3164 KB Output is correct
23 Correct 2 ms 3084 KB Output is correct
24 Correct 2 ms 3416 KB Output is correct
25 Correct 2 ms 3164 KB Output is correct
26 Correct 29 ms 8796 KB Output is correct
27 Correct 28 ms 8272 KB Output is correct
28 Correct 28 ms 8528 KB Output is correct
29 Correct 28 ms 8352 KB Output is correct
30 Correct 28 ms 8468 KB Output is correct