Submission #1082348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082348		vuavisao	Experimental Charges (NOI19_charges)	C++14	100 / 100	32 ms	8540 KiB

charges

#include <bits/stdc++.h>
using namespace std;

const int N = (int) 1e5 + 10;
const char STATE[] = {'A', 'R', '?'};


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

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

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

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

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);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 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);
		}
	}
	
	for (int i = 1; i <= n; ++ i) parent[i] = i;

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

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31