Submission #1055884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055884		rtonbe	Keys (IOI21_keys)	C++17	9 / 100	314 ms	481436 KiB

keys

#include <bits/stdc++.h>
using namespace std;
struct node {
    bool key[32];
    vector<int> adj[32];
    int sz = 0;
    bool dead = false;
};
const int maxn = 3e5 + 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) {
    u = rt(u), v = rt(v);
    if (info[u].sz > info[v].sz) swap(u, v);
    for (int i=0;i<32;i++) {
        while (info[u].adj[i].size() > 0) {
            info[v].adj[i].push_back(info[u].adj[i].back());
            info[u].adj[i].pop_back();
        }
        info[v].key[i] |= info[u].key[i];
        info[u].adj[i].clear();
    }
    info[v].sz += info[u].sz;
    fa[u] = v;
}

bool dfs(int u) {
    bool done = true;
    while (done) {
        done = false;
        u = rt(u);
        vis[u] = 1;
        for (int k=0;k<32;k++) if (info[u].key[k]) {
            int v = -1;
            while (info[u].adj[k].size() > 0) {
                v = rt(info[u].adj[k].back());
                if (u==v) {info[u].adj[k].pop_back(); v = -1; info[u].sz--; continue;}
                else break;
            }
            if (v==-1) continue;
            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++) for (int j=0;j<32;j++) info[i].key[j] = 0;
    for (int i=0;i<n;i++) {
        info[i].key[r[i]] = true;
        fa[i] = i;
    }
    int m = U.size();
    for (int i=0;i<m;i++) {
        info[U[i]].adj[C[i]].push_back(V[i]);
        info[V[i]].adj[C[i]].push_back(U[i]);
        info[U[i]].sz++;
        info[V[i]].sz++;
    }
    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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33