Submission #533092

#	Time	Username	Problem	Language	Result	Execution time	Memory
533092		VodkaInTheJar	Keys (IOI21_keys)	C++17	100 / 100	886 ms	152220 KiB

keys

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include "keys.h"

using namespace std;

const int maxn = 3e5 + 3;

vector <pair <int, int> > adj_all[maxn];
vector <int> adj[maxn], adj_rev[maxn];
vector <int> order;
bool used[maxn];
unordered_set <int> keys[maxn];

int par[maxn], sz[maxn];
inline int find_root(int ver) {
    if (ver == par[ver])
        return ver;

    return par[ver] = find_root(par[ver]);
}

void merge(int a, int b) {
    a = find_root(a), b = find_root(b);
    if (a == b)
        return;

    if (sz[a] < sz[b])
        swap(a, b);

    for (auto i: keys[b])
        keys[a].insert(i);

    sz[a] += sz[b];
    par[b] = a;
}

void dfs(int ver) {
    used[ver] = true;
    for (auto i: adj[ver])
        if (!used[i])
            dfs(i);

    order.push_back(ver);
}

void dfs_rev(int ver, int root) {
    merge(ver, root);
    used[ver] = true;
    for (auto i: adj_rev[ver])
        if (!used[i])
            dfs_rev(i, root);
}

vector <int> comp[maxn];
vector <int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
    int n = (int)r.size(), m = (int)u.size();
    for (int i = 0; i < m; i++) {
        adj_all[v[i]].push_back(make_pair(u[i], c[i]));
        adj_all[u[i]].push_back(make_pair(v[i], c[i]));
    }

    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
        keys[i].insert(r[i]);
    }

        for (int iter = 1; iter <= 4; iter++) {
        for (int i = 0; i < n; i++) {
            adj[i].clear();
            adj_rev[i].clear();
        }

        for (int i = 0; i < n; i++) {
            int root = find_root(i);
            for (auto j: adj_all[i])
                if (keys[root].find(j.second) != keys[root].end()) {
                    adj[root].push_back(find_root(j.first));
                    adj_rev[find_root(j.first)].push_back(root);
                }
        }

        memset(used, false, sizeof(used));
        order.clear();
        for (int i = 0; i < n; i++)
            if (i == find_root(i) && !used[i])
                dfs(i);

        memset(used, false, sizeof(used));
        reverse(order.begin(), order.end());
        for (auto i: order)
            if (!used[i])
                dfs_rev(i, i);
    }

    int mins = INT_MAX;
    vector <int> smallest;
    for (int i = 0; i < n; i++)
        comp[find_root(i)].push_back(i);

    for (int i = 0; i < n; i++)
        if (!comp[i].empty()) {
            bool is = true;
            for (auto j: comp[i])
                for (auto k: adj_all[j])
                    if (keys[i].find(k.second) != keys[i].end())
                        if (find_root(k.first) != i) {
                            is = false;
                            break;
                        }

            if (is) {
                if ((int)comp[i].size() < mins) {
                    mins = comp[i].size();
                    smallest.clear();
                }

                if ((int)comp[i].size() == mins)
                    for (auto j: comp[i])
                        smallest.push_back(j);
            }
        }

    vector <int> ans(n, false);
    for (auto i: smallest)
        ans[i] = true;

    return ans;
}


/*
int n, m;
vector <int> r, u, v, c;
int main() {
    cin >> n >> m;
    r.resize(n), u.resize(m), v.resize(m), c.resize(m);
    for (int i = 0; i < n; i++)
        cin >> r[i];

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

    auto ans = find_reachable({0, 1, 1, 2, 2, 1, 2},{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});

    for (auto i: ans)
        cout << i << " ";
    cout << endl;
}
 */



/*
  4 5
  0 1 1 2
  0 1 0
  0 2 0
  1 2 1
  1 3 0
  3 1 2
 */

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