Submission #1134880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134880		TheInvadr	Experimental Charges (NOI19_charges)	C++20	100 / 100	88 ms	1992 KiB

charges

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int p[200005];
int ra[200005];
int find(int x){
    if(x==p[x])return x;
    return p[x]=find(p[x]);
}
void un(int x,int y){
    int px;
    int py;
    px=find(x);
    py=find(y);
    if(px==py)return;
    if(ra[px]>ra[py]){
        p[py]=px;
    }else if(ra[px]<ra[py]){
        p[px]=py;
    }else{
        ra[px]++;
        p[py]=px;
    }
    return;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<200005;i++)p[i]=i;
    while(m--){
        char t;
        int a,b;
        cin>>t>>a>>b;
        if(t=='A'){
            un(a,n+b);
            un(b,n+a);
        }else if(t=='R'){
            un(a,b);
            un(a+n,b+n);
        }else{
            int p1 = find(a);
            int p2 = find(b);
            if(p1==p2){
                cout<<"R"<<endl;
                continue;
            }
            p1 = find(a+n);
            if(p1==p2){
                cout<<"A"<<endl;
                continue;
            }
            cout<<"?"<<endl;
        }
        
    }
}

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