제출 #1052110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052110		MarwenElarbi	열쇠 (IOI21_keys)	C++17	20 / 100	3050 ms	2097152 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;
	for (int i = 0; i < m; ++i)
	{
		if(c[i]==r[u[i]]){
			rev_adj[v[i]].pb(u[i]);
			adj[u[i]].pb(v[i]);
		}
		if(c[i]==r[v[i]]){
			rev_adj[u[i]].pb(v[i]);
			adj[v[i]].pb(u[i]);
		}
	}
	for (int i = 0; i < n; ++i)
	{
		if(!vis[i]) push(i);
	}
	reverse(order.begin(),order.end());
	memset(vis,0,sizeof vis);
	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){
				parent[i]=p;
				if(i==p) continue;
				sz[p]++;
				colors[p].insert(r[i]);
			}
		}
	}
	for (int i = 0; i < n; ++i)
	{
		adj[i].clear();
		rev_adj[i].clear();
	}
	for (int i = 0; i < m; ++i)
	{
		if(parent[u[i]]==parent[v[i]]) continue;
		int x=parent[u[i]];
		int y=parent[v[i]];
		if(colors[x].count(c[i])){
			rev_adj[y].pb(x);
			adj[x].pb(y);
		}
		if(colors[y].count(c[i])){
			rev_adj[x].pb(y);
			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;
	}
	memset(vis,0,sizeof vis);
	order.clear();
	for (int i = 0; i < n; ++i)
	{
		if(!vis[parent[i]]) push(parent[i]);
	}
	reverse(order.begin(),order.end());
	memset(vis,0,sizeof vis);
	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;
				parent[i]=p;
				sz[p]+=sz[i];
				for(auto v:colors[i]) colors[i].insert(v); 
			}
		}
	}
	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;
	}
	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: 11 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33