Submission #759283

#	Time	Username	Problem	Language	Result	Execution time	Memory
759283		drdilyor	Keys (IOI21_keys)	C++17	20 / 100	3066 ms	25324 KiB

keys

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

vi find_reachable(vi r, vi u, vi v, vi c) {
    int n = r.size();
    int m = u.size();
    vector<vi> adj(n);
    vi count(n);
    for (int root = 0; root < n; root++) {
        vi obtained(n);
        vector<vi> adj(n);
        vi visited;
        vi new_keys;
        auto dfs = [&](auto& dfs, int i)->void {
            if (!obtained[r[i]]) {
                obtained[r[i]] = 1;
                new_keys.push_back(r[i]);
            }
            visited[i] = 1;
            for (int e : adj[i]) {
                if (visited[e]) continue;
                dfs(dfs, e);
            }
        };
        do {
            visited.assign(n, 0);
            new_keys.clear();
            dfs(dfs, root);
            for (int i : new_keys) {
                for (int j = 0; j < m; j++)
                    if (c[j] == i) {
                        adj[u[j]].push_back(v[j]);
                        adj[v[j]].push_back(u[j]);
                    }
            }
        } while (new_keys.size());
        count[root] = accumulate(visited.begin(), visited.end(), 0);
    }
    vi ans(n);
    int mn = *min_element(count.begin(), count.end());
    for (int i = 0;i < n;i++)
        ans[i] = count[i] == mn;
    return ans;
}

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