Submission #491432

#	Time	Username	Problem	Language	Result	Execution time	Memory
491432		Joo	Experimental Charges (NOI19_charges)	C++17	100 / 100	28 ms	2556 KiB

charges

#include <bits/stdc++.h>
using namespace std;


const int N = 2e5+10;
int cp[N], n, Q;

int fi(int x){ return cp[x] = (cp[x] == x) ? x : fi(cp[x]); }

void uni(int u, int v){
    u = fi(u), v = fi(v);
    cp[v] = u;
    return;
}


int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Q;
    for(int i = 1; i <= 2*n; i++) cp[i] = i;

    while(Q--){
        char op; int u, v; cin >> op >> u >> v;

        if(op == 'A'){ //differ
            uni(u, v+n);
            uni(u+n, v);
        } else if (op == 'R'){ //same
            uni(u, v);
            uni(u+n, v+n);
        } else {
            //cout << fi(u) << " " << fi(v) << "  " << fi(u+n) << " " << fi(v+n) << "\n";
            if(fi(u) == fi(v)) cout << "R\n";
            else if(fi(u) == fi(v+n)) cout << "A\n";
            else cout << "?\n";
        }

    }

    return 0;
}

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