제출 #1252315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252315		gry3125	Experimental Charges (NOI19_charges)	C++20	100 / 100	71 ms	1608 KiB

charges

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define all(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
using namespace std;

int sz[100005];
pair<int,bool> par[100005];

pair<int,bool> find(int v) {
	if (par[v].fi == v) return {v, 1};
	auto u = find(par[v].fi);
	if (par[v].se) return u;
	u.se = !u.se; return u;
}
void merge(int a, int b, bool c) {
	auto A = find(a), B = find(b);
	if (A.fi == B.fi) return;
	if (sz[A.fi] < sz[B.fi]) swap(A, B);
	sz[A.fi] += sz[B.fi]; par[B.fi].fi = A.fi;
	if (c == 1) par[B.fi].se = (A.se == B.se);
	else par[B.fi].se = !(A.se == B.se);
}

int main() {
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++) {
		par[i].fi = i; 
		par[i].se = 1; 
		sz[i] = 1;
	}
	while (q--) {
		char c; cin >> c; 
		int a, b; cin >> a >> b; a--; b--;
		if (c == 'A') {merge(a, b, 0); continue;}
		if (c == 'R') {merge(a, b, 1); continue;}
		auto A = find(a), B = find(b);
		if (A.fi != B.fi) {cout << "?\n"; continue;}
		cout << (A.se == B.se ? "R" : "A") << "\n";
	}
    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