Submission #1056548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056548		onbert	Keys (IOI21_keys)	C++17	100 / 100	906 ms	181432 KiB

keys

#include <bits/stdc++.h>
using namespace std;
struct node {
    set<int> key;
    set<pair<int,int>> adj;
    set<int> adj1;
    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 (u==v) return;
    if (info[u].key.size() + info[u].adj.size() + info[u].adj1.size() > info[v].key.size() + info[v].adj.size() + info[v].adj1.size()) swap(u, v);
    for (int x:info[u].key) {
        if (!info[v].key.count(x)) {
            info[v].key.insert(x);
            while (true) {
                pair<int,int> cur = *info[v].adj.lower_bound(make_pair(x, 0));
                if (cur.first!=x) break;
                int V = rt(cur.second);
                info[v].adj.erase(cur);
                if (v!=V) {
                    info[v].adj1.insert(V);
                }
            }
        }
    }
    for (pair<int,int> x:info[u].adj) {
        if (info[v].key.count(x.first)) info[v].adj1.insert(x.second);
        else info[v].adj.insert(x);
    }
    for (int x:info[u].adj1) info[v].adj1.insert(x);
    fa[u] = v;
}
 
bool dfs(int u) {
    while (true) {
        u = rt(u);
        vis[u] = 1;
        int v = -1;
        while (info[u].adj1.size() > 0) {
            v = *info[u].adj1.begin();
            if (u==rt(v)) {info[u].adj1.erase(v); v = -1;}
            else {
                info[u].adj1.erase(v);
                v = rt(v);
                break;
            }
        }
        // cout << u << " " << v << endl;
        if (v==-1) break;
        if (vis[v]==2 || info[v].dead) {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) {merge(u, v); return true;}
        } else {
            u = rt(u);
            info[u].dead = true;
            return false;
        }
    }
    vis[rt(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].adj.insert({INF, INF});
    }
    int m = U.size();
    for (int i=0;i<m;i++) {
        if (r[U[i]]!=C[i]) info[U[i]].adj.insert({C[i], V[i]});
        else info[U[i]].adj1.insert(V[i]);
        if (r[V[i]]!=C[i]) info[V[i]].adj.insert({C[i], U[i]});
        else info[V[i]].adj1.insert(U[i]);
    }
    for (int i=0;i<n;i++) if (!vis[rt(i)]) bool trash = dfs(i);
 
    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;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:90:49: warning: unused variable 'trash' [-Wunused-variable]
   90 |     for (int i=0;i<n;i++) if (!vis[rt(i)]) bool trash = dfs(i);
      |                                                 ^~~~~

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