Submission #1052134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052134		MarwenElarbi	Keys (IOI21_keys)	C++17	9 / 100	3066 ms	42668 KiB

keys

#include <bits/stdc++.h>
using namespace std;
const int nax=2e5+5;
#define pb push_back
#define fi first
#define se second
int parent[nax];
vector<int> adj[nax];
vector<int> rev_adj[nax];
set<int> colors[nax];
int vis[nax];
int sz[nax];
vector<int> order;
void push(int x){
	vis[x]=true;
	for(auto u:adj[x]){
		if(vis[u]) continue;
		push(u);
	}
	order.pb(x);
}
void pull(int x,vector<int>& cur){
	vis[x]=true;
	for(auto u:rev_adj[x]){
		if(vis[u]) continue;
		pull(u,cur);
	}
	cur.pb(x);
}
int dfs(int x,int p){
	for(auto u:adj[x]){
		if(u==p) continue;
		sz[x]+=dfs(u,x);
	}
	return sz[x];
}
int find(int x){
	if(x==parent[x]) return x;
	return parent[x]=find(parent[x]);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n=r.size();
	int m=u.size();
	for (int i = 0; i < n; ++i) colors[i].insert(r[i]);
	for (int i = 0; i < n; ++i) parent[i]=i;
	for (int i = 0; i < n; ++i) sz[i]=1;
	while(true){
		for (int i = 0; i < n; ++i)
		{
			adj[i].clear();
			rev_adj[i].clear();
		}
		for (int i = 0; i < m; ++i)
		{
			if(find(u[i])==find(v[i])) continue;
			int x=parent[u[i]];
			int y=parent[v[i]];
			if(colors[x].count(c[i])){
				adj[x].pb(y);
				rev_adj[y].pb(x);
			}
			if(colors[y].count(c[i])){
				adj[y].pb(x);
				rev_adj[x].pb(y);
			}
		}
		memset(vis,0,sizeof vis);
		for (int i = 0; i < n; ++i)
		{
			vector<int> cur;
			sort(adj[i].begin(),adj[i].end());
			for (int j = 0; j < (int)adj[i].size(); ++j)
			{
				if(j==(int)adj[i].size()-1||adj[i][j]!=adj[i][j+1])
					cur.pb(adj[i][j]);
			}
			adj[i]=cur;
		}
		for (int i = 0; i < n; ++i)
		{
			vector<int> cur;
			sort(rev_adj[i].begin(),rev_adj[i].end());
			for (int j = 0; j < (int)rev_adj[i].size(); ++j)
			{
				if(j==(int)rev_adj[i].size()-1||rev_adj[i][j]!=rev_adj[i][j+1])
					cur.pb(rev_adj[i][j]);
			}
			rev_adj[i]=cur;
		}
		memset(vis,0,sizeof vis);
		order.clear();
		for (int i = 0; i < n; ++i)
		{
			if(!vis[find(i)]) push(find(i));
		}
		reverse(order.begin(),order.end());
		memset(vis,0,sizeof vis);
		bool test=false;
		for(auto u:order){
			if(!vis[u]){
				vector<int> component;
				pull(u,component);
				sort(component.begin(),component.end());
				int p=component[0];
				for(auto i:component){
					if(i==p) continue;
					test=true;
					parent[i]=p;
					sz[p]+=sz[i];
					for(auto v:colors[i]) colors[i].insert(v); 
				}
			}
		}
		if(!test) break;
	}
	for (int i = 0; i < n; ++i)
	{
		adj[i].clear();
		rev_adj[i].clear();
	}
	for (int i = 0; i < m; ++i)
	{
		if(find(u[i])==find(v[i])) continue;
		int x=parent[u[i]];
		int y=parent[v[i]];
		if(colors[x].count(c[i])){
			adj[x].pb(y);
		}
		if(colors[y].count(c[i])){
			adj[y].pb(x);
		}
	}
	for (int i = 0; i < n; ++i)
		{
			vector<int> cur;
			sort(adj[i].begin(),adj[i].end());
			for (int j = 0; j < (int)adj[i].size(); ++j)
			{
				if(j==(int)adj[i].size()-1||adj[i][j]!=adj[i][j+1])
					cur.pb(adj[i][j]);
			}
			adj[i]=cur;
		}
		for (int i = 0; i < n; ++i)
		{
			vector<int> cur;
			sort(rev_adj[i].begin(),rev_adj[i].end());
			for (int j = 0; j < (int)rev_adj[i].size(); ++j)
			{
				if(j==(int)rev_adj[i].size()-1||rev_adj[i][j]!=rev_adj[i][j+1])
					cur.pb(rev_adj[i][j]);
			}
			rev_adj[i]=cur;
		}
	int mn=n;
	memset(vis,0,sizeof vis);
	for (int i = 0; i < n; ++i)
	{
		if(vis[find(i)]) continue;
		dfs(find(i),-1);
		mn=min(mn,sz[find(i)]);
	}
	vector<int> ans(n);
	for (int i = 0; i < n; ++i)
	{
		ans[i]=(sz[find(i)]==mn ? 1 : 0);
	}
	return ans;
}

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