Submission #367647

#	Time	Username	Problem	Language	Result	Execution time	Memory
367647		ritul_kr_singh	Experimental Charges (NOI19_charges)	C++17	100 / 100	32 ms	4972 KiB

charges

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int p[200000], sz[200000];

int parent(int u){
    return p[u] == u ? u : p[u] = parent(p[u]);
}

void merge(int a, int b){
    a = parent(a), b = parent(b);
    if(a==b) return;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, q; cin >> n >> q;
    for(int i=0; i<2*n; ++i){
        sz[i] = 1;
        p[i] = i;
    }
    while(q--){
        char t; cin >> t;
        int x, y; cin >> x >> y;
        --x, --y;
        if(t=='Q'){
            bool rep = parent(2*x) == parent(2*y), att = parent(2*x) == parent(2*y + 1);
            if(rep) cout << "R\n";
            else if(att) cout << "A\n";
            else cout << "?\n";
        }else{
            merge(2*x, 2*y + (t=='A'));
            merge(2*y + (t=='R'), 2*x + (t=='A') + (t=='R'));
        }
//        for(int i=0; i<2*n; ++i) cout << i sp parent(i) nl;
    }
}

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