Submission #486164

#	Time	Username	Problem	Language	Result	Execution time	Memory
486164		niloyroot	Experimental Charges (NOI19_charges)	C++14	100 / 100	29 ms	3404 KiB

charges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
const ll mod = 1000000007;

void solve(){
    ll n; cin>>n;
    ll q; cin>>q;
    ll par[n+1];
    ll sz[n+1];
    bool col[n+1]; // whether it attracts it's parent or not;
    forp(i,1,n){
        par[i]=i;
        sz[i]=1;
        col[i]=0;
    }
    char c; ll a,b,x,y; bool currA,currB;
    forp(i,1,q){
        cin>>c>>a>>b;
        x=a;y=b;
        if(c!='Q'){
            currA=(c=='A'); currB=0;
            while(a!=par[a]){
                currA=(col[a]==1)?(currA^1):currA;
                a=par[a];
            }
            while(b!=par[b]){
                currB=(col[b]==1)?(currB^1):currB;
                b=par[b];
            }
            if(a==b){continue;}
            if(sz[a]<sz[b]){swap(a,b);}
            sz[a]+=sz[b];
            par[b]=a;
            col[b]=(currA!=currB);
        } else {
            currA=currB=0;
            while(a!=par[a]){
                currA=(col[a]==0)?currA:(currA^1);
                a=par[a];
            }
            while(b!=par[b]){
                currB=(col[b]==0)?currB:(currB^1);
                b=par[b];
            }
            if(a!=b){
                cout<<'?'<<newl;
            } else {
                if(currA!=currB){
                    cout<<"A"<<newl;
                } else {
                    cout<<"R"<<newl;
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1; //cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

charges.cpp: In function 'void solve()':
charges.cpp:24:20: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   24 |     char c; ll a,b,x,y; bool currA,currB;
      |                    ^
charges.cpp:24:22: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   24 |     char c; ll a,b,x,y; bool currA,currB;
      |                      ^

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