Submission #495342

#	Time	Username	Problem	Language	Result	Execution time	Memory
495342		Giantpizzahead	Keys (IOI21_keys)	C++17	9 / 100	3021 ms	153916 KiB

keys

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (false) cerr
using namespace std;
using ll = long long;

const int MAXN = 6e5+10;

int N, M;
vector<int> R, ans, ds;
unordered_map<int, vector<int>> adj[MAXN];
unordered_set<int> keys[MAXN];
vector<int> toVisit[MAXN];
vector<int> vis, finalNodes;

void init() {
	rep(i, 0, N) ds[i] = -1;
}

int find(int x) {
	if (ds[x] < 0) return x;
	int r = find(ds[x]);
	ds[x] = r;
	return r;
}

void addVisit(unordered_map<int, vector<int>>& a, unordered_set<int>& k, vector<int>& v) {
	vector<int> temp;
	if (sz(a) < sz(k)) {
		// Iterate through edges
		for (auto& r : a) {
			if (k.count(r.first)) {
				// Key and edges match
				temp.push_back(r.first);
				for (int e : r.second) {
					v.push_back(find(e));
				}
			}
		}
	} else {
		// Iterate through keys
		for (auto& r : k) {
			if (a.count(r)) {
				// Key and edges match
				temp.push_back(r);
				for (int e : a[r]) {
					v.push_back(find(e));
				}
			}
		}
	}
	for (int r : temp) a.erase(r);
}

int merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return a;
	else if (ds[a] < ds[b]) swap(a, b);

	auto adjA = adj[a];
	auto adjB = adj[b];
	auto keysA = keys[a];
	auto keysB = keys[b];
	auto toVisitA = toVisit[a];
	auto toVisitB = toVisit[b];

	// Add to toVisit
	addVisit(adjA, keysB, toVisitA);
	addVisit(adjB, keysA, toVisitB);

	// Merge adj, keys, and toVisit
	if (sz(adjA) < sz(adjB)) {
		adjB.insert(all(adjA));
		adj[b] = adjB;
	} else {
		adjA.insert(all(adjB));
		adj[b] = adjA;
	}
	if (sz(keysA) < sz(keysB)) {
		keysB.insert(all(keysA));
		keys[b] = keysB;
	} else {
		keysA.insert(all(keysB));
		keys[b] = keysA;
	}
	if (sz(toVisitA) < sz(toVisitB)) {
		toVisitB.insert(toVisitB.end(), all(toVisitA));
		toVisit[b] = toVisitB;
	} else {
		toVisitA.insert(toVisitA.end(), all(toVisitB));
		toVisit[b] = toVisitA;
	}

	// Merge a into b
	vis[a] = -1;
	vis[b] = 1;
	ds[b] += ds[a];
	ds[a] = b;
	return b;
}

void dfs(int n) {
	n = find(n);
	if (vis[n] == 2) return;
	debug << "dfs(" << n << ")" << endl;
	rep(i, 0, N) debug << ds[i] << " \n"[i==N-1];
	rep(i, 0, N) {
		debug << i << ": ";
		for (int k : keys[i]) debug << k << " ";
		for (auto r : adj[i]) {
			debug << "(" << r.first << " |";
			for (int e : r.second) debug << " " << e;
			debug << ") ";
		}
		debug << "/ ";
		for (int e : toVisit[i]) debug << e << " ";
		debug << endl;
	}
	debug << endl;
	vis[n] = 1;
	bool isLeaf = true;
	while (!toVisit[n].empty()) {
		int e = find(toVisit[n].back());
		toVisit[n].pop_back();
		debug << "vis " << e << " from " << n << endl;
		if (e == n) continue;
		else if (vis[e] == 0) {
			// Fresh node; start there
			isLeaf = false;
			dfs(e);
		} else if (vis[e] == 1) {
			// Cycle; merge e with this node
			isLeaf = false;
			int newN = merge(e, n);
			dfs(newN);
			return;
		} else if (vis[e] == 2) {
			// Would visit
			isLeaf = false;
		}
		n = find(n);
	}
	if (isLeaf) finalNodes.push_back(n);
	vis[n] = 2;
}

void solve() {
	// Generate initial toVisit
	rep(n, 0, N) {
		keys[n].insert(R[n]);
		if (!adj[n].count(R[n])) continue;
		for (int e : adj[n][R[n]]) {
			toVisit[n].push_back(e);
		}
		adj[n].erase(R[n]);
	}
	int minSize = MAXN;
	unordered_set<int> minRoots;
	rep(n, 0, N) {
		if (vis[find(n)] == 0) {
			dfs(find(n));
			for (int x : finalNodes) {
				int s = -ds[x];
				if (s < minSize) {
					minRoots.clear();
					minSize = s;
				}
				if (s <= minSize) minRoots.insert(x);
			}
			finalNodes.clear();
		}
	}
	rep(n, 0, N) {
		ans[n] = minRoots.count(find(n));
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	N = sz(r), M = sz(u);
    R = r;
	ans.resize(N);
	vis.resize(N);
	ds.resize(N);
	init();
	rep(i, 0, M) {
		adj[u[i]][c[i]].push_back(v[i]);
		adj[v[i]][c[i]].push_back(u[i]);
	}
	solve();
	return ans;
}

/*
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	vector<int> r{0,1,1,2};
	vector<int> u{0,0,1,1,3};
	vector<int> v{1,2,2,3,1};
	vector<int> c{0,0,1,0,2};
    vector<int> ans = find_reachable(r,u,v,c);
	rep(i, 0, sz(ans)) cout << ans[i] << " \n"[i==sz(ans)-1];
    return 0;
}
*/

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