Submission #1259218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259218		biank	Keys (IOI21_keys)	C++20	100 / 100	477 ms	80624 KiB

keys

#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;

const int MAX_N = 3e5 + 9;

int cmp[MAX_N];
vector<ii> adj[MAX_N];
int R[MAX_N];
int keys[MAX_N], t = 1;
vi blocked[MAX_N];
int visited[MAX_N];

int find(int u) {
    if (cmp[u] == u) return u;
    return cmp[u] = find(cmp[u]);
}

vi bfs(int start) {
    queue<int> q;
    q.push(start), visited[start] = t;
    vi toClear, reached;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        reached.pb(u);
        if (find(u) != start) {
            break;
        }
        if (keys[R[u]] < t) {
            keys[R[u]] = t;
            for (int v : blocked[R[u]]) if (visited[v] < t) {
                q.push(v), visited[v] = t;
            }
        }
        for (auto [v, c] : adj[u]) if (visited[v] < t) {
            if (keys[c] == t) q.push(v), visited[v] = t;
            else blocked[c].pb(v), toClear.pb(c);
        }
    }
    for (int c : toClear) blocked[c].clear();
    return reached;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
    int n = sz(r), m = sz(u);
    forn(i, n) cmp[i] = i, R[i] = r[i];
    forn(i, m) adj[u[i]].eb(v[i], c[i]), adj[v[i]].eb(u[i], c[i]);
    bool flag = true;
    while (flag) {
        vector<vi> cmps;
        forn(i, n) if (find(i) == i) {
            cmps.pb(bfs(i)), t++;
        }
        vector<vi> connections(n);
        vi deg(n);
        vector<ii> toJoin;
        for (auto &nodes : cmps) {
            int x = nodes.front(), y = nodes.back();
            if (find(y) != x) toJoin.eb(x, y);
        }
        flag = !toJoin.empty();
        for (auto [x, y] : toJoin) {
            cmp[find(x)] = find(y);
        }
    }
    vector<vi> reached(n);
    int minReacheable = n;
    forn(i, n) if (i == find(i)) {
        reached[i] = bfs(i); t++;
        minReacheable = min(minReacheable, sz(reached[i]));
    }
    vi a(n, 0);
    forn(i, n) if (sz(reached[i]) == minReacheable) {
        for (int j : reached[i]) a[j] = 1;
    }
    return a;
}

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