Submission #623591

#	Time	Username	Problem	Language	Result	Execution time	Memory
623591		Temmie	Keys (IOI21_keys)	C++17	100 / 100	2213 ms	272164 KiB

keys

#include <bits/stdc++.h>

struct Dsu {
	
	std::vector <int> p;
	std::vector <int> size;
	
	Dsu(int s) {
		p.resize(s);
		std::iota(p.begin(), p.end(), 0);
		size.resize(s, 1);
	}
	
	int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	
	void unite(int u, int v) {
		if ((u = find(u)) == (v = find(v))) {
			return;
		}
		p[u] = v;
		//if (size[u] > size[v]) {
			//p[v] = u;
		//} else {
			//p[u] = v;
		//}
	}
	
};

struct Edge {
	
	int u, v, c;
	
};

int n, m;
std::vector <Edge> ed;
std::vector <std::vector <int>> g;
//std::vector <int> p;
Dsu dsu(0), can(0);
std::vector <int> r;
std::vector <bool> last;

bool go() {
	//can = Dsu(n);
	static std::vector <std::unordered_map <int, std::vector <int>>> mp(n);
	static std::vector <std::unordered_set <int>> st(n);
	bool did = false;
	last.assign(n, false);
	for (int i = 0; i < n; i++) {
		if (dsu.find(i) != i) {
			continue;
		}
		std::queue <std::pair <int, int>> q ; q.push ({ i, i });
		while (q.size()) {
			int v = q.front().first;
			int p = q.front().second;
			q.pop();
			if (p != dsu.find(p)) {
				continue;
			}
			if (dsu.find(v) != dsu.find(p)) {
				did = true;
				dsu.unite(p, v);
				continue;
			}
			//if (can.find(v) == can.find(p)) {
				//continue;
			//}
			//can.unite(v, p);
			if (last[v]) {
				continue;
			}
			last[v] = true;
			for (int x : g[v]) {
				int to = ed[x].u ^ ed[x].v ^ v;
				if (st[p].count(ed[x].c)) {
					q.push({ to, p });
				} else {
					mp[p][ed[x].c].push_back(to);
				}
			}
			for (int x : mp[p][r[v]]) {
				q.push({ x, p });
			}
			st[p].insert(r[v]);
			mp[p][r[v]].clear();
		}
	}
	//std::vector <std::vector <int>> in(n);
	//for (int i = 0; i < n; i++) {
		//in[dsu.find(i)].push_back(i);
	//}
	//std::vector <std::vector <int>> ed_of(n);
	//bool did = false;
	//for (int j = 0; j < n; j++) {
		//int i = j;
		//if (dsu.find(i) != i || p[i] != -1) {
			//continue;
		//}
		//for (int v : in[i]) {
			//for (int x : g[v]) {
				//ed_of[ed[x].c].push_back(v ^ ed[x].v ^ ed[x].u);
			//}
		//}
		//std::vector <int> eds;
		//for (int x : in[i]) {
			//for (int y : ed_of[r[x]]) {
				//eds.push_back(y);
			//}
			//ed_of[r[x]].clear();
		//}
		//for (int x : eds) {
			//if (dsu.find(x) == i) {
				//continue;
			//}
			//did = true;
			//if (tree.find(x) == tree.find(i)) {
				//int to = dsu.find(x);
				//while (i != to) {
					//int new_to = dsu.find(p[to]);
					//p[i] = p[to] = p[i];
					//dsu.unite(to, i);
					//i = dsu.find(i);
					//to = new_to;
				//}
			//} else {
				//p[i] = dsu.find(x);
				//tree.unite(x, i);
				//break;
			//}
		//}
		//for (int v : in[i]) {
			//for (int x : g[v]) {
				//ed_of[ed[x].c].clear();
			//}
		//}
	//}
	
	//std::cerr << "did ?= " << did << std::endl;
	
	return did;
}

std::vector <int> find_reachable(std::vector <int> _r, std::vector <int> u, std::vector <int> v, std::vector <int> c) {
	r = _r;
	n = r.size();
	m = c.size();
	ed.resize(m);
	g.resize(n);
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
		ed[i] = { u[i], v[i], c[i] };
	}
	//p.resize(n, -1);
	dsu = Dsu(n);
	//tree = Dsu(n);
	int cnt = 0;
	while (go() && ++cnt < 135);// assert(++cnt < 100);
	//for (int i = 0; i < n; i++) std::cerr << dsu.find(i) << " \n"[i + 1 == n];
	std::vector <int> ans(n, 0);
	for (int i = 0; i < n; i++) {
		ans[dsu.find(i)] += last[i];// += p[dsu.find(i)] == -1;
	}
	int res = 1 << 30;
	for (int x : ans) {
		if (x) {
			res = std::min(res, x);
		}
	}
	std::vector <int> ret(n, 1);
	for (int i = 0; i < n; i++) {
		//if (ans[dsu.find(i)] == res) {
			//ret[i] = 1;
		//}
		if(!last[i] || res != ans[dsu.find(i)]) {
			ret[i] = 0;
		}
	}
	return ret;
}

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