제출 #1193116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193116		loom	Experimental Charges (NOI19_charges)	C++20	100 / 100	39 ms	2372 KiB

charges

#include<bits/stdc++.h>
#define loop(a,b,c,d) for(int a=b; a<c; a+=d)
#define loop2(a,b,c,d) for(int a=b; a>=c; a-=d)
#define bl(i,n) loop(i,0,n,1)
#define bl2(i,n) loop2(i,n,0,1)
#define int long long
#define nl endl
#define g ' '
using namespace std;

pair<int,bool> par[100005];

pair<int,bool> Find(int x){
	if(par[x].first == x) return {x, 0};
	auto xpar = Find(par[x].first);
	return par[x] = {xpar.first, xpar.second ^ par[x].second};
}

void Union(int x, int y, bool c){
	auto xpar = Find(x), ypar = Find(y);
	if(xpar.first == ypar.first) return;
	par[xpar.first] = {ypar.first, c ^ (xpar.second ^ ypar.second)}; 
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);

	int n, q;
	cin>>n>>q;

	bl(i,n) par[i] = {i, 0};

	while(q--){
		char w;
		int a, b;
		cin>>w>>a>>b;
		a--, b--;

		if(w == 'Q'){
			auto apar = Find(a), bpar = Find(b);

			if(apar.first != bpar.first) cout<<"?\n";
			else cout<<((apar.second == bpar.second) ? 'R' : 'A')<<nl;
		}else Union(a, b, w == 'A');
	}
}

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