Submission #598762

#	Time	Username	Problem	Language	Result	Execution time	Memory
598762		Bobaa	Keys (IOI21_keys)	C++17	100 / 100	1265 ms	120464 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;

const int N = 3e5 + 10;
 
int n;
int par[N], sz[N], bad[N], state[N], lst[N]; 
map<int, vector<int>> g[N];
set<int> key[N];
vector<int> to[N];

//dsu
 
int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}
 
void Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    if (key[u].size() + to[u].size() < key[v].size() + to[v].size()) {
		swap(key[u], key[v]);
		swap(to[u], to[v]);
	}
    for (auto w : to[v]) to[u].push_back(w);
    to[v].clear();
    for (auto c : key[v]) if (g[u].find(c) != g[u].end()) {
        for (auto w : g[u][c]) to[u].push_back(w);
        g[u].erase(c);
    }
    for (auto [c, _] : g[v]) {
        if (key[u].find(c) != key[u].end()) for (auto w : g[v][c]) to[u].push_back(w);
		else for (auto w : g[v][c]) g[u][c].push_back(w);
    }
    g[v].clear();
    key[u].insert(key[v].begin(), key[v].end());
    key[v].clear();
}
 
void dfs(int u) {
    state[u] = 0;
    while (1) {
        u = Find(u);
        if (to[u].empty()) break;
        int v = to[u].back();
        to[u].pop_back();
        v = Find(v);
        if (u == v) continue;
        if (state[v] == -1) {
            lst[v] = u;
            dfs(v);
            if (Find(u) != Find(v)) bad[u] = 1;
        } 
		else if (state[v] == 0) {
            int w = u;
            while (1) {
                if (Find(w) == Find(v)) break;
                Union(w, v);
                w = lst[w];
            }
        } 
		else bad[u] = 1;
    }
    state[u] = 1;
}
 
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = c.size();
	auto addedge = [&](int u, int v, int c) {
        if (r[u] == c) to[u].push_back(v);
        else g[u][c].push_back(v);
	};
	for (int i = 0; i < m; ++i) {
        addedge(u[i], v[i], c[i]);
        addedge(v[i], u[i], c[i]);
	}
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		sz[i] = 1;
		key[i].insert(r[i]);
	}
	memset(state, -1, sizeof(state));
    for (int i = 0; i < n; ++i) if (state[i] == -1) dfs(i);
    for (int i = 0; i < n; ++i) if (bad[i]) bad[Find(i)] = 1;
    vector<int> flg(n, 0);
    int ans = 1e9;
    for (int i = 0; i < n; ++i) if (i == Find(i) && !bad[i]) ans = min(ans, sz[i]);
    for (int i = 0; i < n; ++i) if (!bad[Find(i)] && sz[Find(i)] == ans) flg[i] = 1;
    return flg;
}

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