Submission #436596

#	Time	Username	Problem	Language	Result	Execution time	Memory
436596		two_sides	Keys (IOI21_keys)	C++17	37 / 100	671 ms	95180 KiB

keys

#include <bits/stdc++.h>

using namespace std;

namespace {
    struct disjoint_set {
        vector<int> par, siz;

        void init(int n) {
            par.assign(n, -1);
            siz.assign(n, 1);
        }

        int find(int u) {
            if (par[u] < 0) return u;
            return par[u] = find(par[u]);
        }

        bool unite(int u, int v) {
            u = find(u); v = find(v);
            if (u == v) return false;
            par[v] = u; siz[u] += siz[v];
            return true;
        }

        bool same(int u, int v) {
            return find(u) == find(v);
        }
    } roots, forests;

    vector<set<pair<int, int>>> locks;
    vector<vector<int>> unlocks;
    vector<set<int>> keys;
    vector<int> nxt, vis;

    void unite(int u, int v) {
        if (size(unlocks[u]) < size(unlocks[v]))
            swap(unlocks[u], unlocks[v]);
        for (int w : unlocks[v])
            unlocks[u].push_back(w);
        if (size(locks[u]) + size(keys[u])
        < size(locks[v]) + size(keys[v])) {
            swap(locks[u], locks[v]);
            swap(keys[u], keys[v]);
        }
        for (auto edge : locks[v]) {
            if (keys[u].count(edge.first))
                unlocks[u].push_back(edge.second);
            else locks[u].insert(edge);
        }
        for (auto key : keys[v]) {
            auto iter = locks[u].
            lower_bound(make_pair(key, -1));
            while (iter != locks[u].end()
            && iter->first == key) {
                unlocks[u].push_back(iter->second);
                iter = locks[u].erase(iter);
            }
            keys[u].insert(key);
        }
    }

    void dfs(int u) {
        vis[u] = 2;
        if (!vis[nxt[u]]) dfs(nxt[u]);
        else if (vis[nxt[u]] == 2) {
            int v = nxt[u];
            while (u != v) {
                roots.unite(u, v);
                unite(u, v); v = nxt[v];
            }
            while (unlocks[u].size()) {
                int v = unlocks[u].back();
                unlocks[u].pop_back();
                if (forests.unite(v, u)) {
                    nxt[u] = v; break;
                }
                while (!roots.same(u, v)) {
                    unite(u, v = roots.find(v));
                    roots.unite(nxt[v], v);
                }
            }
        }
        vis[u] = 1;
    }
}

vector<int> find_reachable(vector<int> r,
vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size(); locks.resize(n);
    unlocks.resize(n); keys.resize(n);
    nxt.assign(n, -1); vis.resize(n);
    roots.init(n); forests.init(n);
    for (int i = 0; i < u.size(); i++) {
        if (c[i] == r[u[i]]) nxt[u[i]] = v[i];
        if (c[i] == r[v[i]]) nxt[v[i]] = u[i];
        locks[u[i]].emplace(c[i], v[i]);
        locks[v[i]].emplace(c[i], u[i]);
    }
    for (int i = 0; i < n; i++) {
        keys[i].insert(r[i]);
        if (nxt[i] < 0) {
            for (int j = 0; j < n; j++)
                if (nxt[j] < 0) nxt[j] = 1;
                else nxt[j] = 0;
            return nxt;
        }
        forests.unite(nxt[i], i);
    }
    for (int i = 0; i < n; i++)
        if (!vis[i]) dfs(i);
    int res = n;
    for (int i = 0; i < n; i++)
        if (forests.par[i] < 0) {
            int j = roots.find(i);
            res = min(res, roots.siz[j]);
        }
    vis.assign(n, 0);
    for (int i = 0; i < n; i++) {
        int j = forests.find(i);
        if (roots.same(i, j)) {
            j = roots.find(i);
            vis[i] = res == roots.siz[j];
        }
    }
    return vis;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~

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