# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
573709 | Devigo | Experimental Charges (NOI19_charges) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int w = 1000050;
int n, m;
char c;
vector<int> parent((int) 1e7), siz((int) 1e7, 1);
int findpar(int x) {
if(x == parent[x]) return x;
return parent[x] = findpar(parent[x]);
}
void unite(int x, int y) {
x = findpar(x);
y = findpar(y);
if(x == y) return;
if(siz[y] > siz[x]) swap(x, y);
parent[y] = x;
siz[x] += siz[y];
}
signed main() {
cin >> n >> m;
for(int i = 0; i < (int) 1e7; ++i) parent[i] = i;
int x, y;
while(m--) {
cin >> c; cin >> x >> y;
if(c == 'A') {
unite(x, y + w);
unite(x + w, y);
} else if(c == 'R') {
unite(x, y);
unite(x + w, y + w);
} else {
int p, q, s;
p = findpar(x);
q = findpar(y);
r = findpar(x + w);
//s = findpar(y + w);
//if(p == q && p == s) cout << "?";
if (p == q) cout << "R";
else if (p == r) cout << "A";
else cout << "?";
cout << "\n";
}
}
}