Submission #1105918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105918		KK_1729	Experimental Charges (NOI19_charges)	C++17	100 / 100	25 ms	4944 KiB

charges

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

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}

struct UFDS{
	vector<int> link, siz, charge, mark;
	UFDS (int n){
		link.resize(n+1); siz.resize(n+1, 1); charge.resize(n+1); mark.resize(n+1);

		for (int i = 0; i <= n; ++i) link[i] = i;
	}


	int findRoot(int x){
		if (x == link[x]) return x;
		return findRoot(link[x]);
	}

	int OfindCharge(int x){
		if (x == link[x]) return mark[x];
		return mark[x]^OfindCharge(link[x]);
	}

	int findCharge(int x){
		return OfindCharge(x);
	}
	void unitea(int x, int y){
		int xr = findRoot(x), yr = findRoot(y);
		if (xr == yr) return;
		if (findCharge(x) == findCharge(y)){
			if (siz[xr] < siz[yr]) swap(xr, yr);
			link[yr] = xr;
			siz[xr] += siz[yr];
			mark[yr] = 1;
		}else{
			if (siz[xr] < siz[yr]) swap(xr, yr);
			link[yr] = xr;
			siz[xr] += siz[yr];
		}
	}

	void uniter(int x, int y){
		int xr = findRoot(x), yr = findRoot(y);
		if (xr == yr) return;
		if (findCharge(x) == findCharge(y)){
			if (siz[xr] < siz[yr]) swap(xr, yr);
			link[yr] = xr;
			siz[xr] += siz[yr];
		}else{
			if (siz[xr] < siz[yr]) swap(xr, yr);
			link[yr] = xr;
			siz[xr] += siz[yr];
			mark[yr] = 1;
		}
	}
};
void solve(){
	int n, q; cin >> n >> q;
	UFDS ds(n+1);
	// cout << "a" << endl;
	while (q--){
		char t; int a, b; cin >> t >> a >> b;
		if (t == 'A'){
			ds.unitea(a, b);
		}else if (t == 'R'){
			ds.uniter(a, b);
		}else{
			// cout << "i";
			// int a, b; cin >> a >> b;
			if (ds.findRoot(a) != ds.findRoot(b)){
				cout << "?" << endl;
				continue;
			}

			if (ds.findCharge(a) == ds.findCharge(b)){
				cout << "R" << endl;
			}else{
				cout << "A" << endl;
			}
		}
	}
	// FOR(i,1,n+1) cout << ds.findCharge(i) << " ";
	cout << endl;
}
int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	// freopen("in.in", "r", stdin);
	// freopen("out.out", "w", stdout);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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