Submission #1092286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092286		svm	Experimental Charges (NOI19_charges)	C++14	100 / 100	26 ms	2708 KiB

charges

#include <bits/stdc++.h>

#define TASK "charges"

using namespace std;

#define fst first
#define snd second

typedef long long int64;
typedef pair<int, int> pii;

const int MAXN = 1e5 + 55;

pii par[MAXN];

pii find_set(int u) {
    if (par[u].fst == u) return pii(u, 0);
    pii pu = find_set(par[u].fst);
    return par[u] = pii(pu.fst, pu.snd ^ par[u].snd);
}

void join(int u, int v, bool diff) {
    pii pu = find_set(u);
    pii pv = find_set(v);
    if (pu.fst == pv.fst) return;
    par[pv.fst] = pii(pu.fst, pu.snd ^ pv.snd ^ diff);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n, q; cin >> n >> q;
    for (int u = 1; u <= n; u++)
        par[u] = pii(u, 0);
    while (q--) {
        string t; int u, v;
        cin >> t >> u >> v;
        if (t == "Q") {
            pii pu = find_set(u), pv = find_set(v);
            if (pu.fst != pv.fst) {
                puts("?");
                continue;
            }
            puts(pu.snd == pv.snd ? "R" : "A");
            continue;
        }
        join(u, v, (t == "A"));
    }
}

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