Submission #653964

#	Time	Username	Problem	Language	Result	Execution time	Memory
653964		true22	Experimental Charges (NOI19_charges)	C++14	100 / 100	35 ms	4024 KiB

charges

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

typedef int64_t ll;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;

typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)

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

#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

vl lnk, sz, opp;

ll find(ll a) {
    return (a == lnk[a] ? a : lnk[a] = find(lnk[a]));
}

ll unite(ll a, ll b) {
    if(a == -1)
        return b;
    else if(b == -1)
        return a;

    a = find(a);
    b = find(b);

    if(a == b)
        return a;

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

    lnk[b] = a;
    sz[a] += sz[b];
    return a;
}
void solve()
{
    ll n, m;
    cin >> n >> m;
    // cout << n << ' ' << m << nl;

    lnk.resize(n + 1);
    sz.resize(n + 1);
    opp.resize(n + 1);
    fur(i, 0, n) {
        lnk[i] = i;
        sz[i] = 1;
        opp[i] = -1;
    }

    while(m--) {
        char c;
        ll a, b;
        cin >> c >> a >> b;

        if(c == 'A') {
            a = find(a);
            b = find(b);
            if(a == b)
                continue;

            ll c = opp[a]; // a attracts c
            ll d = opp[b]; // b attracts d

            if(c != -1)
                b = unite(b, c); // a attracts b and c
            if(d != -1)
                a = unite(a, d); // b attracts a and d

            opp[a] = b;
            opp[b] = a;
        }
        else if(c == 'R') {
            a = find(a);        
            b = find(b);
            if(opp[a] == b)
                continue;

            ll c = opp[a];
            ll d = opp[b];
    
            c = unite(c, d);
            a = unite(a, b);

            opp[a] = c;
            if(c != -1)
                opp[c] = a;
        }
        else {
            a = find(a);
            b = find(b);

            if(a == b)
                cout << 'R' << nl;
            else if(opp[a] == b || opp[b] == a)
                cout << 'A' << nl;
            else
                cout << '?' << nl;
        }
    }
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll t = 1;
    // cin >> t;
    while(t--)
    {
        solve();
    }
}

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