Submission #558978

#	Time	Username	Problem	Language	Result	Execution time	Memory
558978		nghiass001	Keys (IOI21_keys)	C++17	100 / 100	1128 ms	63328 KiB

keys

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define pii pair<int, int>
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 5;
int n, m, key_in[N], is_key[N], avail[N];
int finished[N], sol[N];
vector<pii> S[N];
vector<int> list_node[N], list_key, Q;

void solve(int u) {
    for(int v : list_key) {
        list_node[v].clear();
    }
    for(int v : Q) {
        is_key[key_in[v]] = 0;
        avail[v] = 0;
    }
    list_key.clear();
    Q.clear();

    int cnt = 1;
    avail[u] = 1;
    Q.push_back(u);
    REP(i, 0, (int)Q.size()) {
        u = Q[i];
        if (!is_key[key_in[u]]) {
            is_key[key_in[u]] = 1;
            for(int v : list_node[key_in[u]]) if (!avail[v]) {
                if (finished[v]) return;
                ++cnt;
                avail[v] = 1;
                Q.push_back(v);
            }
            list_node[key_in[u]].clear();
        }
        for(auto [v, type] : S[u]) if (!avail[v]) {
            if (is_key[type]) {
                if (finished[v]) return;
                ++cnt;
                avail[v] = 1;
                Q.push_back(v);
            }
            else {
                list_key.push_back(type);
                list_node[type].push_back(v);
            }
        }
    }

    for(int v : Q) sol[v] = min(sol[v], cnt);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    m = u.size();
    REP(i, 0, n) key_in[i] = r[i];
    REP(i, 0, m) {
        S[u[i]].emplace_back(v[i], c[i]);
        S[v[i]].emplace_back(u[i], c[i]);
    }

    vector<int> tmp;
    REP(i, 0, n) REP(j, 0, (int)S[i].size()) tmp.push_back(i);
    shuffle(tmp.begin(), tmp.end(), rd);

    int mini = 1e6;
    REP(i, 0, n) sol[i] = 1e6;
    for(int i : tmp) if (!finished[i]) {
        solve(i);
        finished[i] = true;
        mini = min(mini, sol[i]);
    }
    REP(i, 0, n) if (!finished[i]) {
        solve(i);
        finished[i] = true;
        mini = min(mini, sol[i]);
    }

    vector<int> ans(n, 0);
    REP(i, 0, n) ans[i] = (mini == sol[i]);
	return ans;
}

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