Submission #789579

#	Time	Username	Problem	Language	Result	Execution time	Memory
789579		Trunkty	Keys (IOI21_keys)	C++17	9 / 100	460 ms	119972 KiB

keys

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

int n,m;
set<int> vals[300005];
map<int,vector<int>> roads[300005];
vector<int> tovis[300005];
bool vis[300005];
int curr[300005];

// DSU
int root[300005],siz[300005];

int findroot(int x){
	if(x!=root[x]){
		root[x] = findroot(root[x]);
	}
	return root[x];
}

void domerge(int a, int b){
	a = findroot(a);
	b = findroot(b);
	if(a==b){
		return;
	}
	if(siz[a]>siz[b]){
		swap(a,b);
	}
	root[a] = b;
	siz[b] += siz[a];
	for(int i:vals[a]){
		vals[b].insert(i);
	}
	vals[a].clear();
	for(int i:tovis[a]){
		tovis[b].push_back(i);
	}
	tovis[a].clear();
	for(pair<int,vector<int>> i:roads[a]){
		if(vals[b].find(i.first)!=vals[b].end()){
			for(int j:i.second){
				tovis[b].push_back(j);
			}
		}
		else{
			for(int j:i.second){
				roads[b][i.first].push_back(j);
			}
		}
	}
	roads[a].clear();
	curr[b] += curr[a];
}

int toret=-1;

void dfs(int x){
	if(curr[x]){
		toret = x;
		return;
	}
	vis[x] = true;
	curr[x]++;
	while(tovis[x].size()>0){
		int p = tovis[x].back();
		p = findroot(p);
		tovis[x].pop_back();
		dfs(p);
		if(toret!=-1){
			domerge(x,p);
			x = findroot(x);
			p = findroot(p);
			toret = findroot(toret);
			if(toret==x){
				toret = -1;
			}
			else{
				curr[x]--;
				return;
			}
		}
	}
	curr[x]--;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
	n = r.size();
	m = u.size();
	for(int i=0;i<=n-1;i++){
		vals[i].insert(r[i]);
		root[i] = i;
		siz[i] = 1;
	}
	for(int i=0;i<=m-1;i++){
		roads[u[i]][c[i]].push_back(v[i]);
		roads[v[i]][c[i]].push_back(u[i]);
	}
	bool one=false;
	for(int i=0;i<=n-1;i++){
		for(int j:roads[i][r[i]]){
			tovis[i].push_back(j);
		}
		roads[i][r[i]].clear();
		if(tovis[i].size()==0){
			one = true;
		}
	}
	if(one){
		vector<int> ret;
		for(int i=0;i<=n-1;i++){
			if(tovis[i].size()==0){
				ret.push_back(1);
			}
			else{
				ret.push_back(0);
			}
		}
		return ret;
	}
	for(int i=0;i<=n-1;i++){
		if(!vis[i] and root[i]==i){
			dfs(i);
		}
	}
	vector<int> ret;
	int mini=2e9;
	for(int i=0;i<=n-1;i++){
		if(siz[findroot(i)]==1){
			continue;
		}
		mini = min(mini,siz[findroot(i)]);
	}
	for(int i=0;i<=n-1;i++){
		if(siz[findroot(i)]==mini){
			ret.push_back(1);
		}
		else{
			ret.push_back(0);
		}
	}
	return ret;
}

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