Submission #598761

#	Time	Username	Problem	Language	Result	Execution time	Memory
598761		Bobaa	Keys (IOI21_keys)	C++17	9 / 100	583 ms	103124 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std; 

const int maxn = 3e5 + 10; 

int par[maxn], sz[maxn], bad[maxn], state[maxn], lst[maxn]; 
map<int, vector<int>> g[maxn]; 
set<int> key[maxn]; 
vector<int> to[maxn]; 

namespace 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 (g[u].find(c) != g[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(); 
	}
}

using namespace dsu;

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(), m = c.size(); 
	auto adde = [&](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++) {
		adde(u[i], v[i], c[i]); 
		adde(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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33