제출 #997702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997702		0npata	열쇠 (IOI21_keys)	C++17	100 / 100	857 ms	258652 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;
};



const int N = 300'005;

vec<pair<int, int>> g[N];
bool processed[N];
set<int> top;
int node_keys[N];
int ans[N];
State states[N];

void merge(int u, int v) {
	if(states[u].merged.size() < states[v].merged.size()) swap(states[u], states[v]);
	State& s1 = states[u];
	State& s2 = states[v];

	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);
	}
}

int dfs(int u) {
	top.insert(u);

	//TODO: IF this breaks it's because of this reference which might change after merge maybe??
	State& state = states[u];
	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;
		}
		else {
			auto res = dfs(v);
			if(res == -1) {
				for(int w : state.merged) {
					processed[w] = true;
				}
				//cerr << "DFS RETURNED LEAF FOUND" << '\n';
				return -1;
			}
			else {
				merge(u, v);
				state = states[u];
				if(state.merged.find(res) == state.merged.end()) {
					//cerr << "MERGING IT UPWARDS" << '\n';
					return res;
				}
				//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();

	for(int i = 0; i<n; i++) {
		processed[i] = false;
		g[i] = {};
		ans[i] = n;
		node_keys[i] = r[i];
		states[i] = {};
	}

	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]});
	}

	for(int i = 0; i<n; i++) {
		if(processed[i]) continue;
		top = {};
		auto res = dfs(i);
		assert(processed[i]);
		assert(res == -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';

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

	return res;
}

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