Submission #827929

#	Time	Username	Problem	Language	Result	Execution time	Memory
827929		Liudas	Keys (IOI21_keys)	C++17	100 / 100	253 ms	84768 KiB

keys

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

template <int maxN>
struct dsu
{
    int n, parents[maxN], rank[maxN];
    void clear(int size)
    {
        n = size;
        for (int i = 0; i < n; i++)
            parents[i] = i;
        memset(rank, 0, sizeof(int) * n);
    }
    int get(int a) { return parents[a] == a ? a : parents[a] = get(parents[a]); }
    int merge(int a, int b)
    {
        if ((a = get(a)) == (b = get(b)))
            return 0;
        if (rank[a] < rank[b])
        {
            parents[a] = b;
        }
        else
        {
            parents[b] = a;
            if (rank[a] == rank[b])
                rank[a]++;
        }
        return 1;
    }
};
dsu<300000> parent;

template <int maxN, int maxM>
struct graph
{
    struct edge;
    struct vertex
    {
        edge *next;
        int visited, r;
    } vs[maxN], *end = vs + maxN;
    struct edge
    {
        vertex *to;
        edge *next;
        int c;
    } es[maxM], *nextE = es;
    void clear(int n) { memset(vs, 0, sizeof(vertex) * n), end = vs + n, nextE = es; }
    edge *add(int from, int to) { return nextE->to = vs + to, nextE->next = vs[from].next, vs[from].next = nextE++; }

    int round, min, reachSize, ans[maxN], ansSize, key[maxN], noKey[maxM], noKeySize;
    vertex *reach[maxN];
    vector<vertex *> noKeys[maxN];
    vector<int> solve()
    {
        round = 0;
        min = 0x3f3f3f3f;
        ansSize = 0;
        parent.clear(end - vs);

        for (vertex *v = vs; v != end; v++)
        {
            for (int i = 0; i < reachSize; i++)
                key[reach[i]->r] = 0;
            for (int i = 0; i < noKeySize; i++)
                noKeys[noKey[i]].clear();
            reachSize = 0;
            noKeySize = 0;
            round++;

            if (!dfs(v, v))
            {
                if (reachSize < min)
                {
                    min = reachSize;
                    ansSize = 0;
                }
                if (reachSize == min)
                    for (int i = 0; i < reachSize; i++)
                        ans[ansSize++] = reach[i] - vs;
            }
        }

        vector<int> ret(end - vs);
        for (int i = 0; i < ansSize; i++)
            ret[ans[i]] = 1;
        return ret;
    }
    int dfs(vertex *v, vertex *start)
    {
        if (reachSize == min)
            return 1;
        reach[reachSize++] = v;

        v->visited = round;
        if (parent.merge(start - vs, v - vs))
            return 1;

        if (!key[v->r])
        {
            key[v->r] = 1;
            for (vertex *u : noKeys[v->r])
                if (u->visited < round)
                    if (dfs(u, start))
                        return 1;
        }

        for (edge *e = v->next; e; e = e->next)
            if (e->to->visited < round)
            {
                if (key[e->c])
                {
                    if (dfs(e->to, start))
                        return 1;
                }
                else
                {
                    noKey[noKeySize++] = e->c;
                    noKeys[e->c].push_back(e->to);
                }
            }
        return 0;
    }
};
graph<300000, 2 * 300000> g;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    int n = r.size(), m = u.size();
    g.clear(n);

    for (int i = 0; i < n; i++)
        g.vs[i].r = r[i];
    for (int i = 0; i < m; i++)
    {
        g.add(u[i], v[i])->c = c[i];
        g.add(v[i], u[i])->c = c[i];
    }

    return g.solve();
}

void testCase()
{
    int n, m;
    cin >> n >> m;
    vector<int> r(n);
    for (int i = 0; i < n; i++)
        cin >> r[i];

    vector<int> u(m), v(m), c(m);
    for (int i = 0; i < m; i++)
        cin >> u[i] >> v[i] >> c[i];

    auto ans = find_reachable(r, u, v, c);
    for (auto v : ans)
        cout << v << ' ';
}

/*int main()
{
    testCase();
    return 0;
}*/

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