Submission #1063037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063037		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	3058 ms	27760 KiB

keys

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

vector<vector<ii> > L;

int dfs(int n, int m, int s, vi &r) {
    vi viz(n, 0);

    vector<vi> Locked(n);
    vi Q;

    Q.push_back(s);
    set<int> Cul;

    while(!Q.empty()) {
        int u = Q.back();
        Q.pop_back();
        if(!Cul.count(r[u])) {
            for(auto it : Locked[r[u]]) {
                if(!viz[it]) {
                    viz[it] = 1;
                    Q.push_back(it);
                }
            }
            Cul.insert(r[u]);
        }
        for(auto [c, to] : L[u]) {
            if(viz[to]) continue;
            if(Cul.count(c)) {
                viz[to] = 1;
                Q.push_back(to);
            } else {
                Locked[c].push_back(to);
            }
        }
    }
    int re = 0;
    for(auto it : viz) re += it;
    return re;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
    int n = int(r.size()), m = int(u.size());
    L.resize(n);
    for(int i = 0; i < m; ++i) {
        L[u[i]].push_back({c[i], v[i]});
        L[v[i]].push_back({c[i], u[i]});
    }
    vi nr;
    int mi = n;
    for(int i = 0; i < n; ++i) {
        nr.push_back(dfs(n, m, i, r));
        mi = min(mi, nr.back());
    }
    vi re;
    for(int i = 0; i < n; ++i)
        re.push_back(nr[i] == mi);
    return re;
}

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