Submission #1292481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292481		chaitanyamehta	Lost Array (NOI19_lostarray)	C++20	0 / 100	2 ms	332 KiB

lostarray

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

struct DSU {
    vector<int> par;
    vector<int> size;
    void init(int n){
        par.resize(n + 1);
        size.assign(n + 1 , 1);
        for(int i = 0;i<=n;i++)par[i] =i;
    }
    int find(int u){
        if(par[u] == u) return u;
        return par[u] = find(par[u]);
    }
    void Union(int u , int v){
        int paru = find(u); int parv = find(v);

        if(paru == parv){
            return;
        }
        if(size[paru] < size[parv]){
            par[paru] = parv;
            size[parv] += size[paru];
        }
        else{
            par[parv] = paru;
            size[paru] += size[parv];
        }

    }
};

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, q;
    cin >> n >> q;
    DSU dsu;
    dsu.init(n);
    
    // Use map for sparse relations (keys are sorted pairs of roots)
    map<pii, int> relations;  // or unordered_map with hash for pii
    
    while (q--) {
        char t;
        cin >> t;
        int u, v;
        cin >> u >> v;
        
        int pu = dsu.find(u), pv = dsu.find(v);
        if (t == 'Q') {
            if (pu == pv) {
                cout << "R\n";
            } else {
                pii key = {min(pu, pv), max(pu, pv)};
                cout << (relations[key] ? "A\n" : "?\n");
            }
        } else if (t == 'A') {
            if (pu != pv) {  // Ignore if same
                pii key = {min(pu, pv), max(pu, pv)};
                relations[key] = 1;
            }
        } else {  // 'C' - union
            if (pu != pv) {
                // TODO: Merge relations from pu and pv into new root
                // E.g., iterate over current neighbors of pu/pv and add to new root
                dsu.Union(u, v);
            }
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 48