Submission #1219360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219360		thangdz2k7	Keys (IOI21_keys)	C++20	37 / 100	3094 ms	20844 KiB

keys

#include <bits/stdc++.h>

using namespace std;
using Vi = vector <int>;

vector <int> find_reachable(Vi R, Vi U, Vi V, Vi C){
    int n = R.size(), m = C.size();
    vector <Vi> adj(n);
    for (int i = 0; i < m; ++ i){
        adj[U[i]].push_back(i);
        adj[V[i]].push_back(i);
    }

    vector <vector <int>> con(n);
    vector <int> hk(n), qu, vis(n);

    auto add = [&](int u) -> void {

        if (hk[R[u]] == 0){
            hk[R[u]] = 1;
            while (con[R[u]].size()){
                int v = con[R[u]].back();
                con[R[u]].pop_back();
                if (!vis[v]){
                    vis[v] = 1;
                    qu.push_back(v);
                }
            }
        }

        for (int id : adj[u]){
            int v = U[id] ^ V[id] ^ u;
            int c = C[id];
            if (!vis[v]){
                if (hk[c]) {
                    vis[v] = 1;
                    qu.push_back(v);
                }
                else con[c].push_back(v);
            }
        }
    };

    vector <int> p(n, 0);

    for (int r = 0; r < n; ++ r){

        for (int t = 0; t < n; ++ t){
            hk[t] = 0, vis[t] = 0;
            con[t].clear();
        }

        vis[r] = 1; qu.push_back(r);
        while (qu.size()){
            int u = qu.back(); qu.pop_back();
            add(u); p[r] ++;
        }
    }

    int Min = *min_element(p.begin(), p.end());

    vector <int> a(n);
    for (int i = 0; i < n; ++ i){
        if (p[i] == Min) a[i] = 1;
        else a[i] = 0;
    }

    return a;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33