Submission #333053

#	Time	Username	Problem	Language	Result	Execution time	Memory
333053		banterbry	Experimental Charges (NOI19_charges)	C++17	46 / 100	1092 ms	8200 KiB

charges

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
typedef pair<int,int> pi;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
	cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
	string cur = "";
	for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
	string nxt = names.substr(cur.size()+2);
	cerr << cur << " = " << head << ", ";
	__f(nxt, tail...);
}

const int mxn = 1e5 + 5;
int n, q, par[mxn], sz[mxn];
bool charge[mxn];
vector<int> adj[mxn];

int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
}
bool same(int x, int y) {return root(x) == root(y);}
void unite(int x, int y) {
    x = root(x), y = root(y);
    if (x == y) return;
    par[x] = y; 
    sz[y] += sz[x];
}

void dfs(int x, int p) {
	charge[x] = !charge[x];
	for (auto i: adj[x]) {
		if (i == p) continue;
		dfs(i, x);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1;
	while (q--) {
		char op; int a, b;
		cin >> op >> a >> b;
		if (op == 'Q') {
			if (!same(a, b)) cout << '?';
			else cout << (charge[a] == charge[b] ? 'R' : 'A');
			cout << '\n';
		} else {
			if (op == 'R') {
				if (charge[a] != charge[b]) {
					if (sz[a] > sz[b]) swap(a, b);
					dfs(a, a);
				}
			} else {	
				if (charge[a] == charge[b]) {
					if (sz[a] > sz[b]) swap(a, b);
					dfs(a, a);
				}
			}
			if (!same(a, b)) {
				unite(a, b);
				adj[a].pb(b);
				adj[b].pb(a);
			}
		}
	}
	return 0;
}
		

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