제출 #1082344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082344		vuavisao	Experimental Charges (NOI19_charges)	C++14	100 / 100	29 ms	8796 KiB

charges

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31