Submission #997687

#	Time	Username	Problem	Language	Result	Execution time	Memory
997687		0npata	Keys (IOI21_keys)	C++17	37 / 100	3063 ms	70416 KiB

keys

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

#define vec vector

struct State {
	map<int, vec<int>> locked_edgs;
	vec<int> stk;
	set<int> merged;
	set<int> keys;
};

State& merge(State& s1, State& s2) {
	if(s1.merged.size() < s2.merged.size()) swap(s1, s2);
	for(int u : s2.merged) {
		s1.merged.insert(u);
	}
	for(int k : s2.keys) {
		if(s1.locked_edgs.find(k) != s1.locked_edgs.end()) {
			for(int v : s1.locked_edgs[k]) {
				s1.stk.push_back(v);
			}
			s1.locked_edgs.erase(k);
		}
		s1.keys.insert(k);
	}
	for(auto edgs : s2.locked_edgs) {
		int k = edgs.first;
		if(s1.keys.find(k) != s1.keys.end()) {
			for(int v : edgs.second) {
				s1.stk.push_back(v);
			}
		}
		else {
			for(int v : edgs.second) {
				s1.locked_edgs[k].push_back(v);
			}
		}
	}
	for(int u : s2.stk) {
		s1.stk.push_back(u);
	}

	return s1;
}

pair<int, State> dfs(int u, set<int>& top, vec<bool>& processed, vec<vec<pair<int, int>>>& g, vec<int>& node_keys, vec<int>& ans) {
	top.insert(u);

	State state{};
	state.keys.insert(node_keys[u]);
	state.merged.insert(u);

	cerr << "U: " << u << '\n';
	for(auto edg : g[u]) {
		int v = edg.first;
		int k = edg.second;

		if(state.keys.find(k) != state.keys.end()) state.stk.push_back(v);
		else { state.locked_edgs[k].push_back(v); }
	}

	while(state.stk.size() > 0) {
		int v = state.stk.back();
		state.stk.pop_back();
		cerr << "V: " << v << '\n';

		if(processed[v]) {
			for(int w : state.merged) {
				processed[w] = true;
			}
			cerr << "HIT PROCESSED" << '\n';
			return {-1, {}};
		}
		else if(state.merged.find(v) != state.merged.end()) {
			cerr << "IN MERGED" << '\n';
			continue;
		}
		else if(top.find(v) != top.end()) {
			cerr << "AT TOP" << '\n';
			return {v, state};
		}
		else {
			auto res = dfs(v, top, processed, g, node_keys, ans);
			if(res.first == -1) {
				for(int w : state.merged) {
					processed[w] = true;
				}
				cerr << "DFS RETURNED LEAF FOUND" << '\n';
				return {-1, {}};
			}
			else {
				State new_state = move(merge(state, res.second));
				state = move(new_state);
				if(state.merged.find(res.first) == state.merged.end()) {
					cerr << "MERGING IT UPWARDS" << '\n';
					return {res.first, move(state)};
				}
				cerr << "MERGED" << '\n';
			}
		}
	}

	cerr << "IS A PREORDER LEAF" << '\n';
	for(int v : state.merged) {
		ans[v] = state.merged.size();
		processed[v] = true;
	}
	return {-1, {}};
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size();
	int m = u.size();

	vec<vec<pair<int, int>>> g(n);

	for(int i = 0; i<m; i++) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}

	vec<bool> processed(n);
	vec<int> ans(n, n);

	for(int i = 0; i<n; i++) {
		if(processed[i]) continue;
		set<int> top;
		auto res = dfs(i, top, processed, g, r, ans);
		assert(processed[i]);
		assert(res.first == -1);
	}

	int mn = n;
	cerr << "----DEBUG----" << '\n';
	for(int i = 0; i<n; i++) {
		mn = min(mn, ans[i]);
		cerr << ans[i] << ' ';
	}
	cerr << '\n';

	cerr << "-------------" << '\n';

	for(int i = 0; i<n; i++) {
		ans[i] = ans[i] == mn;
	}

	return ans;
}

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