| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1280357 | jackofall718 | Experimental Charges (NOI19_charges) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <chrono>
#define ll long long int
#define endl '\n'
#define vn vector<ll>
#define vi vector<pair <ll,ll>>
using namespace std;
using namespace std::chrono;
const int MAX_N = 1e9 + 7;
#define pii pair<ll,ll>
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define pb push_back
#define srt(vp) sort(vp.begin(), vp.end())
vn link;
vector <vn> adj;
vn status;
vn sizes;
ll find (ll n){
while ( n != link[n])n=link[n];
return n;
};
ll same(ll x, ll y){
return find(x)==find(y);
};
void unite(ll x, ll y){
x = find(x);
y = find(y);
if (sizes[x]<sizes[y])swap(x,y);
sizes[x]+=sizes[y];
link[y]=x;
adj[x].insert(adj[x].end(),adj[y].begin(),adj[y].end());//gpt for this impl
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto start = high_resolution_clock::now();
ll n,q;
cin>>n>>q;
link.resize(n+1);
adj.resize(n+1);
status.resize(n+1,1);
sizes.resize(n+1);
for (int i=1;i<=n;i++)sizes[i]=1;
for (int i=1;i<=n;i++)link[i]=i;
for (int i=1;i<=n;i++)adj[i].pb(i);
for (int i=0;i<q;i++){
char a;
ll b,c;
cin>>a>>b>>c;
if (a=='A'){
if (find(b)==find(c))continue;
if ((status[b]^1) == status[c]) {
unite(b,c);
}
else{
b = find(b);
c= find(c);
if (sizes[b]<sizes[c])swap(b,c);
for (auto &x:adj[c])status[x]^=1;
unite(b,c);
}
}
else if (a=='R'){
if (find(b)==find(c))continue;
if (status[b]==status[c]){
unite(b,c);
}
else{
b = find(b);
c= find(c);
if (sizes[b]<sizes[c])swap(b,c);
for (auto &x:adj[c])status[x]^=1;
unite(b,c);
}
}
else{
if (find(b) != find(c))cout<<"?"<<endl;
else if (status[b]==status[c])cout<<"R"<<endl;
else cout<<"A"<<endl;
}
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
//cout << "Time taken by function: " << duration.count() << " microseconds" << endl;
return 0;
}