Submission #1055885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055885		rtonbe	Keys (IOI21_keys)	C++17	37 / 100	3126 ms	1793356 KiB

keys

#include <bits/stdc++.h>
using namespace std;
struct node {
    int root;
    set<int> key;
    set<pair<int,int>> adj;
    bool dead = false;
};
const int maxn = 2e5 + 5, INF = 1e9;
int n, m;
node info[maxn];
int fa[maxn];
int vis[maxn];
int rt(int u) {
    if (fa[u]==u) return u;
    else return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
    int root = info[v].root;
    if (info[u].key.size() + info[v].adj.size() > info[u].key.size() + info[v].adj.size()) swap(u, v);
    for (int x:info[u].key) info[v].key.insert(x);
    for (pair<int,int> x:info[u].adj) info[v].adj.insert(x);
    info[v].root = root;
    fa[u] = v;
}

bool dfs(int u) {
    bool done = true;
    while (done) {
        done = false;
        u = rt(u);
        vis[u] = 1;
        for (int k:info[u].key) {
            pair<int,int> cur;
            int v;
            while (true) {
                cur = *info[u].adj.lower_bound(make_pair(k, 0));
                if (cur.first!=k) break;
                v = rt(cur.second);
                if (u==v) {info[u].adj.erase(cur); continue;}
                else break;
            }
            if (cur.first!=k) continue;
            // cout << u << " " << v << endl;
            if (vis[v]==2) {info[u].dead = true; return false;}
            if (vis[v]==1) {merge(u, v); return true;}
            if (dfs(v)) {
                v = rt(v);
                if (rt(u) == v) {done = true; break;}
                else {merge(u, v); return true;}
            } else {
                info[u].dead = true;
                return false;
            }
        }
    }
    vis[u] = 2;
    return false;
}

vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
	n = r.size();
    for (int i=0;i<n;i++){
        info[i].key.insert(r[i]);
        fa[i] = i;
        info[i].root = i;
        info[i].adj.insert({INF, INF});
    }
    int m = U.size();
    for (int i=0;i<m;i++) {
        info[U[i]].adj.insert({C[i], V[i]});
        info[V[i]].adj.insert({C[i], U[i]});
    }
    for (int i=0;i<n;i++) if (!vis[i]) dfs(i);

    // for (int i=0;i<n;i++) cout << rt(i) << " "; cout << endl;

    int sz[n];
    for (int i=0;i<n;i++) sz[i] = 0;
    for (int i=0;i<n;i++) if (!info[rt(i)].dead) {
        sz[rt(i)]++;
    }
    int mn = INF;
    for (int i=0;i<n;i++) if (!info[rt(i)].dead) {
        mn = min(sz[rt(i)], mn);
    }
    vector<int> ans(n, 0);
    for (int i=0;i<n;i++) ans[i] = (!info[rt(i)].dead && sz[rt(i)]==mn);
    return ans;
}

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