Submission #832906

#	Time	Username	Problem	Language	Result	Execution time	Memory
832906		amunduzbaev	Keys (IOI21_keys)	C++17	39 / 100	1303 ms	76160 KiB

keys

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

#define ar array
typedef long long ll;
//~ #define int ll

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();
	
	vector<vector<ar<int, 2>>> edges(n);
	for(int i=0;i<m;i++){
		edges[u[i]].push_back({v[i], c[i]});
		edges[v[i]].push_back({u[i], c[i]});
	}
	
	int res = n + 1;
	vector<int> mask(n);
	vector<int> ans;
	
	if(n <= 2000 && m <= 2000 && false){
		vector<int> used(n), cviz(n);
		vector<vector<int>> q;
		int cnt = 0;
		
		for(int i=0;i<n;i++){
			fill(used.begin(), used.end(), 0);
			fill(cviz.begin(), cviz.end(), 0);
			q.assign(n, vector<int>());
			cnt = 0;
			
			queue<int> qq;
			qq.push(i);
			
			while(!qq.empty()){
				cnt++;
				int u = qq.front(); qq.pop();
				
				used[u] = 1;
				if(!cviz[r[u]]){
					cviz[r[u]] = 1;
					for(auto x : q[r[u]]){
						if(!used[x]){
							used[x] = 1;
							qq.push(x);
						}
					}
				}
				
				for(auto [x, c] : edges[u]){
					if(used[x]) continue;
					if(cviz[c]){
						used[x] = 1;
						qq.push(x);
					} else {
						//~ assert(false);
						q[c].push_back(x);
					}
				}
			}
			
			if(res > cnt) res = cnt, ans.clear();
			if(res == cnt) ans.push_back(i);
		}
		
		fill(used.begin(), used.end(), 0);
		for(auto x : ans) used[x] = 1;
		
		return used;
	}
	
	for(int i=0;i<n;i++){
		mask[i] |= (1 << r[i]);
	}
	
	vector<int> tin(n), fup(n), cmp(n), ss;
	for(int T=0;T<30;T++){
		int t = 0;
		fill(cmp.begin(), cmp.end(), 0);
		fill(tin.begin(), tin.end(), 0);
		fill(fup.begin(), fup.end(), 0);
		ss.clear();
		
		function<void(int)> dfs = [&](int u){
			tin[u] = fup[u] = ++t;
			ss.push_back(u);
			
			for(auto [x, c] : edges[u]){
				if(!(mask[u] >> c & 1)) continue;
				if(!tin[x]) {
					dfs(x);
					fup[u] = min(fup[u], fup[x]);
				} else if(!cmp[x]){
					fup[u] = min(fup[u], tin[x]);
				}
			}
			
			if(tin[u] == fup[u]){
				vector<int> tmp;
				int x, tot = 0;
				do{
					x = ss.back(); ss.pop_back();
					tmp.push_back(x);
					tot |= mask[x];
				}while(x != u);
				
				for(auto x : tmp){
					//~ cout<<x<<" ";
					cmp[x] = 1;
					mask[x] = tot;
				}
				
				//~ cout<<"\n";
			}
		};
		
		for(int i=0;i<n;i++){
			if(cmp[i]) continue;
			dfs(i);
		}
		//~ cout<<"\n";
	}
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<n;j++) cout<<(mask[i] >> j & 1);
		//~ cout<<"\n";
	//~ }
	
	int t = 0, last = 0;
	ss.clear();
	fill(cmp.begin(), cmp.end(), 0);
	fill(tin.begin(), tin.end(), 0);
	fill(fup.begin(), fup.end(), 0);
	function<void(int)> dfs = [&](int u){
		tin[u] = fup[u] = ++t;
		ss.push_back(u);
		
		for(auto [x, c] : edges[u]){
			if(!(mask[u] >> c & 1)) continue;
			if(!tin[x]) {
				dfs(x);
				fup[u] = min(fup[u], fup[x]);
			} else if(!cmp[x]){
				fup[u] = min(fup[u], tin[x]);
			}
		}
		
		if(tin[u] == fup[u]){
			last++;
			int x;
			do{
				x = ss.back(); ss.pop_back();
				cmp[x] = last;
				
				//~ cout<<x<<" ";
			}while(x != u);
			//~ cout<<"\n";
		}
	};
	
	vector<vector<int>> g(n + 1);
	for(int i=0;i<n;i++){
		if(cmp[i]) continue;
		dfs(i);
	}
	
	vector<int> sz(n + 1);
	for(int i=0;i<n;i++){
		sz[cmp[i]]++;
		for(auto [x, c] : edges[i]){
			if((mask[i] >> c & 1) && cmp[i] != cmp[x]){
				g[cmp[i]].push_back(cmp[x]);
			}
		}
	}
	
	vector<int> viz(n + 1), used(n);
	
	for(int i=1;i<=last;i++){
		if(g[i].empty()){
			if(res > sz[i]) res = sz[i], ans.clear();
			if(res == sz[i]) ans.push_back(i);
		}
	}
	
	for(auto x : ans){
		viz[x] = 1;
	}
	
	for(int i=0;i<n;i++){
		if(viz[cmp[i]]) used[i] = 1;
	}
	
	return used;
}

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