제출 #442303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442303		Stickfish	열쇠 (IOI21_keys)	C++17	9 / 100	1903 ms	133848 KiB

keys

#include <vector>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <cassert>
using namespace std;

const int MAXN = 3e5 + 123;
vector<pair<int, int>> edg[MAXN];
int keyget[MAXN];
bitset<MAXN> used;

vector<int> component[MAXN];
int rcomponent[MAXN];
vector<int> edg0[MAXN];
vector<int> redg0[MAXN];

void dfs1(int v, vector<int>& rtout){
	used[v] = 1;
	for(auto u : edg0[v]){
		if(used[u])
			continue;
		dfs1(u, rtout);
	}
	rtout.push_back(v);
}

void dfs2(int v, vector<int>& compincl){
	used[v] = 1;
	compincl.push_back(v);
	for(auto u : redg0[v]){
		if(used[u])
			continue;
		dfs2(u, compincl);
	}
}	

void update_edg0(int n, int nstart){
	for(int v = 0; v < n; ++v){
		edg0[v].clear();
		redg0[v].clear();
	}

	for(int v = 0; v < nstart; ++v){
		for(auto [u, c] : edg[v]){
			if(rcomponent[u] == rcomponent[v])
				continue;
			if(keyget[rcomponent[v]] & (1 << c)){
				edg0[rcomponent[v]].push_back(rcomponent[u]);
				redg0[rcomponent[u]].push_back(rcomponent[v]);
			}
		}
	}
}

int condensate(int n, int nstart){
	used.reset();
	vector<int> rtout;
	for(int i = 0; i < n; ++i){
		if(used[i])
			continue;
		dfs1(i, rtout);
	}
	used.reset();

	vector<vector<int>> newcomponent;
	reverse(rtout.begin(), rtout.end());
	for(auto v : rtout){
		if(used[v])
			continue;
		newcomponent.push_back({});
		dfs2(v, newcomponent.back());
	}
	int n0 = newcomponent.size();
	vector<int> newkeyget(n0, 0);

	for(int i = 0; i < n0; ++i){
		vector<int>& comp = newcomponent[i];
		for(auto v : comp){
			newkeyget[i] |= keyget[v];
			for(auto v0 : component[v]){
				rcomponent[v0] = i;
			}
		}
	}
	for(int i = 0; i < n0; ++i){
		keyget[i] = newkeyget[i];
		component[i].clear();
	}
	for(int v = 0; v < nstart; ++v)
		component[rcomponent[v]].push_back(v);
	update_edg0(n, nstart);
	return n0;
}

vector<int> solve_small(int n){
	int nstart = n;
	for(int i = 0; i < n; ++i){
		rcomponent[i] = i;
		component[i].push_back(i);
	}
	update_edg0(n, n);
	int cnt = 0;
	//cout << "BLYAT\n";
	while(true){
		assert(cnt++ < 35);
		int n0 = condensate(n, nstart);
		if(n == n0)
			break;
		n = n0;
	}
	//cout << "BLYAT\n";
	//for(int i = 0; i < n; ++i){
		//cout << "---" << i << "---\n";
		//for(auto v : component[i]){
			//cout << v << ' ';
		//}
		//cout << '\n' << edg0[i].size() << '\n';
	//}
	vector<int> ans;
	unsigned ansvl = MAXN;
	for(int i = 0; i < n; ++i){
		if(edg0[i].size())
			continue;
		if(ansvl > component[i].size()){
			ansvl = component[i].size();
			ans = component[i];
		} else if(ansvl == component[i].size()){
			for(auto v : component[i])
				ans.push_back(v);
		}
	}
	//cout << ansvl << '\n';
	return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();
	int maxr = 0;
	for(int i = 0; i < n; ++i){
		keyget[i] = r[i];
		maxr = max(maxr, r[i]);
	}
	for(int i = 0; i < m; ++i){
		edg[u[i]].push_back({v[i], c[i]});
		edg[v[i]].push_back({u[i], c[i]});
		maxr = max(maxr, c[i]);
	}
	//if(n <= 0000 && m <= 2000){
		//vector<int> ans = solve_quad(n);
		//int mn = *min_element(ans.begin(), ans.end());
		//for(int i = 0; i < n; ++i)
			//ans[i] = (ans[i] == mn);
		//return ans;
	//} else if(maxr <= 29){
		for(int i = 0; i < n; ++i)
			keyget[i] = (1 << keyget[i]);
		vector<int> ans = solve_small(n);
		vector<int> rans(n, 0);
		for(auto v : ans)
			rans[v] = 1;
		return rans;
	//}
}

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