Submission #1292476

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

lostarray

// https://oj.uz/problem/view/NOI19_charges
#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(){
    int n , q;
    cin >> n >> q;
    vector<vector<int>> a(n + 1 , vector<int>(n + 1 , 0));
    DSU dsu;
    dsu.init(n);
    while(q--){
        char t;
        cin>>t;
        int u , v;cin>>u>>v;
        
        if(t == 'Q'){
            int paru = dsu.find(u);
            int parv = dsu.find(v);

            if(paru == parv){
                cout << "R\n";
            }
            else{
                if(a[paru][parv] == 1){
                    cout << "A\n";
                }
                else{
                    cout << "?\n";
                }
            }
        }
        else if(t == 'A'){
            int paru = dsu.find(u) , parv = dsu.find(v);

            a[paru][parv] = 1 , a[parv][paru] = 1;
        }
        else{
            dsu.Union(u , v);
        }
    }
}

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