Submission #1285586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285586		lyra_g13	Experimental Charges (NOI19_charges)	C++20	100 / 100	18 ms	3608 KiB

charges

#include <bits/stdc++.h>
using ll = long long;
class djf{
    public:
    ll n;
    std::vector<ll> par , size;
    djf(ll n ) : n(n) , par(n+1) , size(n+1){
        for(int i = 0 ; i < n; i++){
            par[i] = i;
            size[i] = i;
        }
    }

    ll root(ll x){
        if(par[x] == x){
            return x;
        }
        return root(par[x]);
    }

    void merge(ll u ,ll v){
        u = root(u);
        v = root(v);
        if(u == v){
            return;
        }
        if(size[u] < size[v]){
            std::swap(u , v);
        }
        // u is bigger than v 
        par[v] = u;
        size[u] = size[u] + size[v];
    }

};
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n , q;
    std::cin >> n >> q;
    djf s(2*n);
    while(q--){
        char t;
        ll a, b;
        std::cin >> t >> a >> b;
        if(t == 'A'){
          s.merge( a, b+n);
          s.merge(b , a+n);
        }
        else if( t == 'R'){
            s.merge(a , b);
            s.merge(a+n , b+n);
        }
        else{
            if(s.root(a)  == s.root(b)){
                std::cout << "R\n";
            }
            else if(s.root(a)  == s.root(b+n)){
                std::cout << "A\n";
            }
            else{
                std::cout << "?\n";
            }
        }
    }
}

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