Submission #437140

#	Time	Username	Problem	Language	Result	Execution time	Memory
437140		ivan100sic	Keys (IOI21_keys)	C++17	37 / 100	2614 ms	682516 KiB

keys

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

using vi = vector<int>;

struct grana {
    int x, y, c;
};

struct cvor {
    vector<int> v;
    set<int> c;
};

struct bidigraf {
    vector<cvor> v;
    vector<grana> e;
};

struct digraf {
    vector<vi> e;

    vi idx, low, inst, st;
    int dt;
    vector<vi> comps;

    void dfs(int x) {
        idx[x] = low[x] = ++dt;
        inst[x] = 1;
        st.push_back(x);
        for (int y : e[x]) {
            if (idx[y] == 0) {
                dfs(y);
                low[x] = min(low[x], low[y]);
            } else if (inst[y]) {
                low[x] = min(low[x], idx[y]);
            }
        }

        if (idx[x] == low[x]) {
            vi comp;
            while (1) {
                int t = st.back();
                st.pop_back();
                inst[t] = 0;
                comp.push_back(t);
                if (t == x) {
                    break;
                }
            }
            comps.push_back(comp);
        }
    }

    void scc() {
        dt = 0;
        const int n = e.size();
        low = inst = idx = vi(n);
        st = {};
        comps = {};
        for (int i=0; i<n; i++) {
            if (!idx[i]) {
                dfs(i);
            }
        }
    }

    vi rikverc(const vi& b) {
        const int n = e.size();
        vector<vi> f(n);
        for (int i=0; i<n; i++) {
            for (int j : e[i]) {
                f[j].push_back(i);
            }
        }

        vi q, vis(n);
        size_t qs = 0;
        for (int x : b) {
            q.push_back(x);
            vis[x] = 1;
        }

        while (qs != q.size()) {
            int x = q[qs++];
            for (int y : f[x]) {
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push_back(y);
                }
            }
        }

        return vis;
    }
};

vector<vi> naj;

void prijavi(const vi& a) {
    if (naj.empty() || naj[0].size() == a.size()) {
        naj.push_back(a);
    } else if (naj[0].size() > a.size()) {
        naj = {a};
    }
}

void resi(const bidigraf& bd) {
    // napravi prvo digraf
    digraf d;
    const int n = bd.v.size();

    d.e.resize(n);
    for (auto [x, y, c] : bd.e) {
        if (bd.v[x].c.count(c)) {
            d.e[x].push_back(y);
        }
        if (bd.v[y].c.count(c)) {
            d.e[y].push_back(x);
        }
    }

    vi rikverc;

    // ima izolovanih cvorova?
    for (int i=0; i<n; i++) {
        if (d.e[i].empty()) {
            rikverc.push_back(i);
            prijavi(bd.v[i].v);
        }
    }

    d.scc();
    auto vis = d.rikverc(rikverc);

    bidigraf mali;
    vi mapa(n, -1);

    for (const auto& comp : d.comps) {
        if (vis[comp[0]]) continue;
        cvor t;
        for (int x : comp) {
            const auto& cx = bd.v[x].c;
            const auto& vx = bd.v[x].v;
            t.c.insert(cx.begin(), cx.end());
            t.v.insert(t.v.end(), vx.begin(), vx.end());
            mapa[x] = (int)mali.v.size();
        }
        mali.v.emplace_back(move(t));
    }

    for (auto [x, y, c] : bd.e) {
        if (mapa[x] != -1 && mapa[y] != -1 && mapa[x] != mapa[y]) {
            mali.e.push_back({mapa[x], mapa[y], c});
        }
    }

    if (!mali.v.empty()) {
        resi(mali);
    }
}

vi izvestaj(int n) {
    vi a(n);
    for (const auto& v : naj) {
        for (int x : v) {
            a[x] = 1;
        }
    }
    return a;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
    bidigraf bd;
    const int n = r.size();
    const int m = u.size();
    bd.v.resize(n);
    bd.e.resize(m);
    for (int i=0; i<n; i++) {
        bd.v[i] = {{i}, {r[i]}};
    }

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

    resi(bd);
    return izvestaj(n);
}

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