Submission #1020950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020950		mdn2002	Keys (IOI21_keys)	C++17	37 / 100	3048 ms	29152 KiB

keys

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size(), m = u.size(), st;
    vector<int> vis(n), did(n), p(n);
    vector<vector<pair<int, int>>> gr(n);
    vector<vector<int>> vv(n);

    for (int i = 0; i < m; i ++) {
        gr[u[i]].push_back({v[i], c[i]});
        gr[v[i]].push_back({u[i], c[i]});
    }
    function<void(int)> dfs = [&] (int x) {
        vis[x] = 1, did[r[x]] = 1;
        p[st] ++;
        while (vv[r[x]].size()) {
            int u = vv[r[x]].back();
            vv[r[x]].clear();
            if (vis[u] == 0) dfs(u);
        }
        for (auto [u, c] : gr[x]) {
            if (vis[u]) continue;
            if (did[c]) dfs(u);
            else vv[c].push_back(u);
        }
    };
    int mn = 1e9;
    for (int i = 0; i < n; i ++) {
        vis.assign(n, 0);
        did.assign(n, 0);
        st = i;
        dfs(i);
        for (int j = 0; j < n; j ++) vv[j].clear();
        mn = min(mn, p[i]);
    }
    vector ans(n, 0);
    for (int i = 0; i < n; i ++) {
        if (mn == p[i]) ans[i] = 1;
    }
    return ans;
}

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