Submission #689771

#	Time	Username	Problem	Language	Result	Execution time	Memory
689771		zeroesandones	Experimental Charges (NOI19_charges)	C++17	100 / 100	29 ms	4064 KiB

charges

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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define all(x) (x).begin(), (x).end()

#define sc second
#define fr first
#define pb push_back

ll link[100005] = {};
ll sz[100005] = {};
ll opp[100005] = {};

ll find(ll x) {
    return (link[x] == x ? x : link[x] = find(link[x]));
}

ll unite(ll a, ll b) {
    a = find(a);
    b = find(b);

    if(a == b)
        return a;

    if(sz[a] < sz[b])
        swap(a, b);

    sz[a] += sz[b];
    link[b] = a;
    return a;
}

void setA(ll a, ll b){
    a = find(a);
    b = find(b);
    if(a == b)
        return;
    if(opp[a] == -1)
        opp[a] = b;
    else
        opp[a] = unite(opp[a], b);

    if(opp[b] == -1)
        opp[b] = a;
    else
        opp[b] = unite(opp[b], a);
}

bool areA(ll a, ll b) {
    a = find(a);
    b = find(b);
    if(opp[a] != -1 && find(opp[a]) == b)
        return true;
    return false;
}

void setR(ll a, ll b) {
    a = find(a);
    b = find(b);

    if(areA(a, b))
        return;
    if(a == b)
        return;

    ll o;
    if(opp[a] != -1 && opp[b] != -1)
        o = unite(opp[a], opp[b]);
    else if(opp[a] != -1)
        o = find(opp[a]);
    else if(opp[b] != -1)
        o = find(opp[b]);
    else
        o = -1;

    ll fin = unite(a, b);
    opp[fin] = o;
}

char check(ll a, ll b) {
    if(find(a) == find(b))
        return 'R';
    if(areA(a, b))
        return 'A';
    return '?';
}

void solve()
{
    int n, q;
    cin >> n >> q;

    FOR(i, 1, n + 1) {
        link[i] = i;
        sz[i] = 1;
        opp[i] = -1;
    }

    while(q--) {
        char t;
        int a, b;
        cin >> t >> a >> b;

        if(t == 'A')
            setA(a, b);
        else if(t == 'R')
            setR(a, b);
        else
            cout << check(a, b) << nl;
    }
}

int main()
{
    // clock_t start, end;
    // start = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    // end = clock();
    // cout << nl << "Time : " << double(end - start)/double(CLOCKS_PER_SEC) << 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