제출 #1285534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285534		lyra_g13	Experimental Charges (NOI19_charges)	C++20	43 / 100	1096 ms	2060 KiB

charges

#include <bits/stdc++.h>
using ll = long long;
class djf{
    public:
    ll n;
    std::vector<ll> par;
  
    djf(ll n) : n(n) , par(n+1) {
        for(int i = 1 ; i<=n ; i++){
            par[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;
        par[v] = u;
    }
};

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 c;
        ll a , b;
        std::cin >> c >>  a >> b;

        if(c == 'A'){
            s.merge(a, b+n);
            s.merge(a+n , b);
        }
        else if(c == '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: 0 / 14
• Subtask 4: 0 / 12
• Subtask 5: 25 / 25
• Subtask 6: 0 / 31