Submission #440082

#	Time	Username	Problem	Language	Result	Execution time	Memory
440082		koioi.org-koosaga	열쇠 (IOI21_keys)	C++17	0 / 100	2581 ms	50392 KiB

keys

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 400005;

struct disj{
	int pa[MAXN];
	void init(){
		iota(pa, pa + MAXN, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

vector<int> bycmp[MAXN];
set<int> keys[MAXN];
set<pi> gph[MAXN];
int comp[MAXN], nxt[MAXN];

int find(int x){
	return comp[x] = (comp[x] == x ? x : find(comp[x]));
}

void merge_to(int u, int v){
	u = find(u);
	if(u == v) return;
	comp[u] = v;
	for(auto &i : keys[u]) keys[v].insert(i);
	for(auto &i : gph[u]) gph[v].insert(i);
	keys[u].clear();
	gph[u].clear();
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {	
	int n = sz(r);
	for(int i = 0; i < n; i++) keys[i].insert(r[i]);
	for(int i = 0; i < sz(u); i++){
		gph[u[i]].emplace(c[i], v[i]);
		gph[v[i]].emplace(c[i], u[i]);
	}
	disj.init();
	iota(comp, comp + MAXN, 0);
	vector<int> ans(n);
	for(int i = 0; i < n; i++){
		ans[i] = 1;
		for(auto &[j, w] : gph[i]){
			if(r[i] == j){
				ans[i] = 0;
				nxt[i] = w;
			}
		}
	}
	if(count(all(ans), 1) != 0) return ans;
	for(int i = 0; i < n; i++){
		if(find(i) != i) continue;
		if(i == nxt[i]) continue;
		if(!disj.uni(i, nxt[i])){
			for(int j = nxt[i]; ; j = nxt[j]){
				disj.uni(j, n);
				merge_to(j, n);
				if(j == i) break;
			}
			auto it = gph[n].begin();
			nxt[n] = n;
			while(it != gph[n].end()){
				int k, v;
				tie(k, v) = *it;
				if(keys[n].find(k) != keys[n].end()){
					if(find(v) == find(n)) it = gph[n].erase(it);
					else{	
						nxt[n] = find(v);
						break;
					}
				} else it++;
			}
			n++;
		}
	}
	for(int j = 0; j < n; j++){
		bycmp[find(j)].push_back(j);
	}
	fill(all(ans), 1e9);
	for(int j = 0; j < n; j++){
		if(sz(bycmp[j]) && find(nxt[j]) == find(j)){
			for(auto &i : bycmp[j]){
				if(i < sz(ans)) ans[i] = sz(bycmp[j]);
			}
		}
	}
	int val = *min_element(all(ans));
	for(auto &i : ans){
		i = (i == val);
	}
	return ans;
}

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