Submission #333067

#	Time	Username	Problem	Language	Result	Execution time	Memory
333067		banterbry	Experimental Charges (NOI19_charges)	C++17	100 / 100	36 ms	4076 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, sz[mxn];
pi par[mxn];

pi root(int x) {
    if (par[x].first == x) return pi(x, 0);
    pi ct = root(par[x].first);
    return par[x] = pi(ct.first, ct.second ^ par[x].second);
}
bool same(int x, int y) {return root(x) == root(y);}
void unite(int x, int y, int charge) {
    pi xx = root(x), yy = root(y);
   	int a = xx.first, b = yy.first;
   	if (a == b) return;
   	if (sz[a] < sz[b]) swap(a, b);
   	sz[a] += sz[b];
   	par[b].first = a;
   	par[b].second = xx.second ^ yy.second ^ charge;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) par[i] = pi(i, 1), sz[i] = 1;
	while (q--) {
		char op; int a, b;
		cin >> op >> a >> b;
		if (op == 'Q') {
			pi aa = root(a);
			pi bb = root(b);
			if (aa.first != bb.first) cout << "?\n";
			else if (aa.second == bb.second) cout << "R\n";
			else cout << "A\n";
		} else {
			if (op == 'A') unite(a, b, 1);
			else unite(a, b, 0);
		}
	}
	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