Submission #789602

#	Time	Username	Problem	Language	Result	Execution time	Memory
789602		Trunkty	Keys (IOI21_keys)	C++17	9 / 100	744 ms	295552 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];
set<int> rvals[300005];
map<int,bool> cant[30005];

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(rvals[a].size()>rvals[b].size()){
		swap(a,b);
	}
	root[a] = b;
	for(int i:rvals[a]){
		rvals[b].insert(i);
	}
	rvals[a].clear();
	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;
		rvals[i].insert(i);
	}
	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;
	for(int i=0;i<=n-1;i++){
		ret.push_back(0);
	}
	for(int i=0;i<=m-1;i++){
		if(findroot(u[i])==findroot(v[i])){
			continue;
		}
		cant[findroot(u[i])][c[i]] = true;
		cant[findroot(v[i])][c[i]] = true;
	}
	int mini=2e9;
	for(int i=0;i<=n-1;i++){
		bool yes = true;
		for(int j:rvals[i]){
			for(int k:vals[j]){
				if(cant[j][k]){
					yes = false;
				}
			}
		}
		if(yes and rvals[i].size()>0){
			mini = min(mini,(int)rvals[i].size());
		}
	}
	for(int i=0;i<=n-1;i++){
		bool yes = true;
		for(int j:rvals[i]){
			for(int k:vals[j]){
				if(cant[j][k]){
					yes = false;
				}
			}
		}
		if(yes and mini==rvals[i].size()){
			for(int j:rvals[i]){
				ret[j] = 1;
			}
		}
	}
	return ret;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |   if(yes and mini==rvals[i].size()){
      |              ~~~~^~~~~~~~~~~~~~~~~

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