Submission #446632

#	Time	Username	Problem	Language	Result	Execution time	Memory
446632		crackersamdjam	Keys (IOI21_keys)	C++17	9 / 100	1548 ms	2097156 KiB

keys

#include "keys.h"

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using pii = pair<int, int>;
int constexpr MM = 3e5+5;

int n, m;

vector<int> r;

vector<int> adj[MM];
vector<int> adj2[MM];

int dfn[MM], low[MM], t, id[MM];
bool ins[MM];
stack<int> stk;
vector<int> scc[MM];
set<int> newkeys[MM], donekeys[MM];
map<int, vector<int>> to[MM];

// which weakly connected component
// this is different from id[], which is scc "root"
int par[MM];

int find(int x){
	while(x != par[x])
		x = par[x], par[x] = par[par[x]];
	return x;
}

void merge(int a, int b){
	// merges b into a
	if(size(newkeys[b]) > size(newkeys[a]))
		swap(newkeys[a], newkeys[b]);
	for(auto i: newkeys[b])
		newkeys[a].insert(i);

	if(size(donekeys[b]) > size(donekeys[a]))
		swap(donekeys[a], donekeys[b]);
	for(auto i: donekeys[b])
		donekeys[a].insert(i);

	if(size(to[a]) > size(to[b]))
		swap(to[a], to[b]);
	for(auto &[i, v]: to[b]){
		to[a][i].insert(to[a][i].end(), all(v));
	}

	if(size(scc[a]) > size(scc[b]))
		swap(scc[a], scc[b]);
	scc[a].insert(scc[a].end(), all(scc[b]));

	par[find(b)] = find(a);
}

void dfs(int cur){
	dfn[cur] = low[cur] = ++t;
	stk.push(cur);
	ins[cur] = 1;
	
	for(auto u: adj[cur]){
		if(!dfn[u]){
			dfs(u);
			low[cur] = min(low[cur], low[u]);
		}
		else if(ins[u])
			low[cur] = min(low[cur], dfn[u]);
	}
	
	if(dfn[cur] == low[cur]){
		int u = -1;
		while(u != cur){
			u = stk.top(); stk.pop();
			ins[u] = 0;
			id[u] = cur;
			merge(cur, u);
		}
	}
}

vector<int> find_reachable(vector<int> _r, vector<int> a, vector<int> b, vector<int> c){
	r = move(_r);
	n = size(r);
	m = size(a);
	vector<int> res(n);

	for(int i = 0; i < m; i++){
		if(c[i] == r[a[i]]){
			adj[a[i]].emplace_back(b[i]);
			// pr("edge", a[i], b[i]);
		}
		else{
			to[a[i]][c[i]].emplace_back(b[i]);
		}
		if(c[i] == r[b[i]]){
			adj[b[i]].emplace_back(a[i]);
			// pr("edge", a[i], b[i]);
		}
		else{
			to[b[i]][c[i]].emplace_back(a[i]);
		}
	}

	for(int i = 0; i < n; i++){
		par[i] = i;
		newkeys[i].insert(r[i]);
		scc[i].emplace_back(i);
	}

	for(int i = 0; i < n; i++){
		if(!dfn[i]){
			dfs(i);
		}
	}

	for(int i = 0; i < n; i++){
		for(int j: adj[i]){
			if(id[i] != id[j]){
				adj2[id[i]].emplace_back(id[j]);
			}
		}
	}

	// each scc root...
	vector<int> roots;
	for(int i = 0; i < n; i++){
		if(!size(adj2[i])){
			roots.emplace_back(i);
			pr("add rt", i);
		}
	}

	for(auto rt: roots){
		while(size(newkeys[rt])){
			auto i = *newkeys[rt].begin();
			newkeys[rt].erase(i);
			if(donekeys[rt].count(i)) continue;
			donekeys[rt].insert(i);
			for(auto u: to[rt][i]){
				if(find(u) == find(rt)){
					merge(rt, u);
				}
				else{
					merge(u, rt);
					break;
				}
			}
		}
	}

	int ans = 1e9;
	for(auto rt : roots){
		if(find(rt) == rt){
			int s = size(scc[rt]);
			pr("check sz", rt, s);
			if(s < ans){
				ans = s;
			}
		}
	}
	for(auto rt : roots){
		if(find(rt) == rt){
			int s = size(scc[rt]);
			if(s == ans){
				pr("scc", rt);
				for(auto j: scc[rt]){
					pr("j", j);
					res[j] = 1;
				}
			}
		}
	}
	return res;
}

#ifdef LOCAL
namespace me{
	void go(){
		int n, m;
		cin>>n>>m;
		vector<int> r(n), a(m), b(m), c(m);
		for(int i = 0; i < n; i++)
			cin>>r[i];
		for(int i = 0; i < m; i++){
			cin>>a[i]>>b[i]>>c[i];
		}
		auto res = find_reachable(r, a, b, c);
		for(int i = 0; i < size(res); i++)
			cout<<res[i]<<' ';
	}
}
int main(){
	me::go();
}
#endif

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