Submission #676479

#	Time	Username	Problem	Language	Result	Execution time	Memory
676479		penguin133	Experimental Charges (NOI19_charges)	C++17	100 / 100	39 ms	8524 KiB

charges

#include <bits/stdc++.h>
using namespace std;
int p[100005], C[100005];
vector<int>v[100005];
int getr(int x){
	if(p[x] == x)return x;
	else return p[x] = getr(p[x]);
}
void merge(int a, int b, int c){
	int pa = a, pb= b;
	a = getr(a); b = getr(b);
	if(a != b){
		if(v[a].size() > v[b].size()){
			p[b] = a;
			for(auto i : v[b])v[a].push_back(i);
			if(c != (C[pa] ^ C[pb]))for(auto i : v[b])C[i] = 1 - C[i];
		}
		else{
			p[a] = b;
			for(auto i : v[a])v[b].push_back(i);
			if(c != (C[pa] ^ C[pb]))for(auto i : v[a])C[i] = 1 - C[i];
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)C[i] = 1, p[i] = i, v[i].push_back(i);
	while(q--){
		char a;
		int b,c;
		cin >> a >> b >> c;
		if(a == 'R')merge(b,c,0);
		else if(a == 'A')merge(b,c,1);
		else{
			if(getr(b) != getr(c))cout << "?\n";
			else cout << (((C[b] ^ C[c]) == 1) ? "A\n" : "R\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