Submission #568368

#	Time	Username	Problem	Language	Result	Execution time	Memory
568368		kartel	Keys (IOI21_keys)	C++17	100 / 100	1028 ms	142628 KiB

keys

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "keys.h"
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

const int N = 3e5 + 500;

vector <pair <int, int> > g[N];
set <int> unlocked[N], colors[N];
set <pair <int, int> > locked[N];
int pr[N], prc[N], cnt[N];
int mk[N], to[N];
int n, m, root[N];
bool answer[N];
vector <int> r;

void get(int c, int u) {
    while (1) {
        auto it = locked[u].lower_bound(make_pair(c, -1));
        if (it == locked[u].end() || it -> F != c) {
            break;
        }
        unlocked[u].insert(it -> S);
        locked[u].erase(it);
    }
}

int fc(int v) {return (prc[v] == v ? v : prc[v] = fc(prc[v]));}
void link_cyc(int v, int u) {
    v = fc(v); u = fc(u);
    if (v == u) {
        return;
    }

    if (sz(unlocked[v]) + sz(locked[v]) + sz(colors[v]) > sz(unlocked[u]) + sz(locked[u]) + sz(colors[u])) {
        swap(u, v);
    }
    for (auto x : unlocked[v]) {
        unlocked[u].insert(x);
    }
    for (auto x : locked[v]) {
        if (colors[u].count(x.F)) {
            unlocked[u].insert(x.S);
        } else {
            locked[u].insert(x);
        }
    }

    for (auto x : colors[v]) {
        if (!colors[u].count(x)) {
            colors[u].insert(x);
            get(x, u);
        }
    }
    prc[v] = u;
    cnt[u] += cnt[v];
}

int f(int v) {return (pr[v] == v ? v : pr[v] = f(pr[v]));}
void link(int v, int u) {
    v = f(v); u = f(u);
    if (v == u) {
        return;
    }
    pr[v] = u;
}

void go(int c) {
    int v = root[c], rt = root[c];
    while (!mk[v]) {
        mk[v] = 1;
        link_cyc(v, to[v]);
        v = to[v];
    }

    while (sz(unlocked[fc(rt)])) {
        int u = fc(*unlocked[fc(rt)].begin());
        unlocked[fc(rt)].erase(unlocked[fc(rt)].begin());

        if (u == fc(rt)) {
            continue;
        }

        if (f(u) != f(rt)) {
            answer[c] = 0;
            mk[fc(rt)] = 0;
            to[fc(rt)] = u;
            link(u, rt);
            break;
        }
        while (!mk[u]) {
            mk[u] = 1;
            link_cyc(u, rt);
            u = to[u];
        }
    }
}

vector <int> find_reachable(vector <int> _r, vector <int> u, vector <int> v, vector <int> c) {
    r = _r;
    n = sz(r); m = sz(u);

    for (int i = 0; i < m; i++) {
        g[u[i]].pb({v[i], c[i]});
        g[v[i]].pb({u[i], c[i]});
    }

    vector <int> ans(n, 0);
    bool ret = 0;
    for (int i = 0; i < n; i++) {
        to[i] = -1;
        prc[i] = i; cnt[i] = 1;
        pr[i] = i;
        colors[i].insert(r[i]);
        for (auto [u, c] : g[i]) {
            if (r[i] == c) {
                to[i] = u;
                unlocked[i].insert(u);
            } else {
                locked[i].insert({c, u});
            }
        }
        if (to[i] == -1) {
            ans[i] = 1;
            ret = 1;
        }
    }
    if (ret) {
        return ans;
    }

    int cmp = 0;
    for (int i = 0; i < n; i++) {
        if (mk[i]) {
            continue;
        }

        vector <int> nodes;
        int v = i;
        while (!mk[v]) {
            mk[v] = 1;
            nodes.pb(v);
            link(v, to[v]);
            v = to[v];
        }

        if (mk[v] == 1) {
            root[cmp] = v;
            cmp++;
        }
        for (auto v : nodes) {
            mk[v] = 2;
        }
    }
    for (int i = 0; i < n; i++) {
        mk[i] = 0;
    }

    for (int i = 0; i < cmp; i++) {
        answer[i] = 1;
        go(i);
    }

    int mn = 1e9;
    for (int i = 0; i < cmp; i++) {
        if (!answer[i]) {
            continue;
        }
        mn = min(mn, cnt[fc(root[i])]);
    }

    set <int> cmps;
    for (int i = 0; i < cmp; i++) {
        if (answer[i] && cnt[fc(root[i])] == mn) {
            cmps.insert(fc(root[i]));
        }
    }
    for (int i = 0; i < n; i++) {
        if (cmps.count(fc(i))) {
            ans[i] = 1;
        }
    }
    return ans;
}

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