Submission #522263

#	Time	Username	Problem	Language	Result	Execution time	Memory
522263		blue	Experimental Charges (NOI19_charges)	C++17	100 / 100	26 ms	3356 KiB

charges

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 100'000;
using vi = vector<int>;
using pii = pair<int, int>;

struct disjoint_set
{
	vector<pii> parent = vector<pii>(1+mx);
	vi subtree = vi(1+mx, 1);
	vi flip = vi(1+mx, 0);

	disjoint_set()
	{
		for(int i = 1; i <= mx; i++) parent[i] = {i, 0};
	}

	pii root(int u)
	{
		if(parent[u].first == u) return {u, 0};
		else
		{
			pii pr = root(parent[u].first);
			pr.second ^= parent[u].second;
			parent[u] = pr;
			return pr;
		}
	}

	void join(int u, int v, bool b)
	{
		pii up = root(u), vp = root(v);
		if(up.first == vp.first) return;

		if(subtree[up.first] < subtree[vp.first]) swap(up, vp);
		subtree[up.first] += subtree[vp.first];
		parent[vp.first] = {up.first, b ^ up.second ^ vp.second};
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, Q;
	cin >> N >> Q;

	disjoint_set DS;

	for(int q = 1; q <= Q; q++)
	{
		char T;
		int A, B;
		cin >> T >> A >> B;

		if(T == 'A') DS.join(A, B, 1);
		else if(T == 'R') DS.join(A, B, 0);
		else 
		{
			pii AP = DS.root(A), BP = DS.root(B);
			if(AP.first != BP.first) cout << "?\n";
			else if(AP.second == BP.second) cout << "R\n";
			else cout << "A\n";
		}
	}
}

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