Submission #388544

#	Time	Username	Problem	Language	Result	Execution time	Memory
388544		strawberry2005	Experimental Charges (NOI19_charges)	C++17	32 / 100	30 ms	3988 KiB

charges

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 1e9+7;
#define deb(x) cout<<#x<<": "<<x<<endl

int iceil(int a, int b) {
  return (a + b - 1) / b;
}

vector<int> parent1,parent2,done;

int find_ds(int x){
    if(parent1[x]==x) return(x);
    return(parent1[x]=find_ds(parent1[x]));
}

void union_ds(int a,int b){
    a=find_ds(a);b=find_ds(b);
    if(a!=b) parent1[b]=a;
}

int find_ds2(int x){
    if(parent2[x]==x) return(x);
    return(parent2[x]=find_ds2(parent2[x]));
}

void union_ds2(int a,int b){
    a=find_ds2(a);b=find_ds2(b);
    if(a!=b) parent2[b]=a;
}


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(20);

    #ifdef strawberryshaker2005
        freopen("input.txt", "r", stdin);
    #endif

    int n,k;
    cin>>n>>k;
    parent1.resize(n);done.assign(n,0);parent2.resize(n);
    for(int i=0;i<n;i++) parent1[i]=i;
    for(int i=0;i<n;i++) parent2[i]=i;
    for(int i=0;i<k;i++){
        char a;int b,c;
        cin>>a>>b>>c;b--;c--;
        if(a=='Q'){
            if(done[b]==0||done[c]==0) cout<<"?\n";
            else{
                if(find_ds(b)==find_ds(c)) cout<<"R\n";
                else if(find_ds2(b)==find_ds2(c)) cout<<"A\n";
                else cout<<"?\n";
            }
        }
        else if(a=='R'){
            union_ds(b,c);done[b]=1;done[c]=1;
        }
        else{
            done[b]=1;done[c]=1;
            union_ds2(b,c);
        }
    } 



    return(0);
    
}

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