Submission #647499

#	Time	Username	Problem	Language	Result	Execution time	Memory
647499		LeonaRaging	Experimental Charges (NOI19_charges)	C++14	100 / 100	49 ms	8436 KiB

charges

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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;

int n, q, sign[maxn];

struct DisjointSet {
    int par[maxn];
    vector<int> mySet[maxn];
    DisjointSet(int n) {
        for (int i = 1; i <= n; i++)
            par[i] = i, mySet[i].pb(i);
    }
    int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    bool join(int u, int v, int type) {
        int flag = sign[u] == sign[v];
        u = find(u); v = find(v);
        if (u == v) return 0;
        if (mySet[v].size() > mySet[u].size()) 
            swap(mySet[u], mySet[v]);
        for (int x : mySet[v]) {
            if (type == flag) sign[x] ^= 1;
            mySet[u].pb(x);
        }
        mySet[v].clear();
        par[v] = u;
        return 1;
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> q;
    memset(sign, 1, sizeof sign);
    DisjointSet Dsu(n);
    for (int i = 1; i <= q; i++) {
        char type; int u, v; cin >> type >> u >> v;
        if (type == 'Q') {
            if (Dsu.find(u) != Dsu.find(v)) cout << '?';
            else cout << (sign[u] == sign[v] ? 'R' : 'A');
            cout << '\n';
        }
        else Dsu.join(u, v, (type == 'R' ? 0 : 1));
    }
}

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