Submission #601806

#	Time	Username	Problem	Language	Result	Execution time	Memory
601806		Apiram	Split the Attractions (IOI19_split)	C++14	33 / 100	352 ms	29608 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int>parent;
	vector<int>sz;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
		}
	}
	int findsets(int v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int u,int v){
		u = findsets(u);
		v = findsets(v);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		parent[v] = u;
		sz[u]+=sz[v];
		return true;
	}
};
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<bool>articulation_point(n,false);
	int m = (int)p.size();
	vector<set<int>>adj(n);
	for (int i = 0;i<m;++i){
		if (p[i] == q[i])continue;
		adj[p[i]].insert(q[i]);
		adj[q[i]].insert(p[i]);
	}
	vector<int>brr;
	brr.push_back(a);
	brr.push_back(b);
	brr.push_back(c);
	vector<int>ord(3);
	iota(ord.begin(),ord.end(),0);
	sort(ord.begin(),ord.end(),[&](int i,int j){
		return brr[i] < brr[j];
	});
	sort(brr.begin(),brr.end());
	vector<int>ans(n,0);
	if (m == n - 1){
		vector<int>sz(n);
		vector<int>parent(n,-1);
		function<void(int)>dfs_tree =[&](int u){
			sz[u] = 1;
			for (auto x:adj[u]){
				if (x == parent[u])continue;
				parent[x] = u;
				dfs_tree(x);
				sz[u]+=sz[x];
			}
		};
		dfs_tree(0);
		vector<int>order(n);
		iota(order.begin(),order.end(),0);
		sort(order.begin(),order.end(),[&](int i,int j){
			return sz[i] < sz[j];
		});
		int index = -1;
		for (int i = 0;i<n;++i){
			if (sz[order[i]] >= brr[0] && n - sz[order[i]] >=brr[1]){
				index = i;
				break;
			}
			else if (sz[order[i]]>=brr[1] && n - sz[order[i]]>=brr[0]){
				index = i;
				break;
			}
		}
		if (index == -1)return ans;
		int v = 0;
		function<void(int,int)>mark = [&](int u,int c){
			if (v<=0)return;
			if (ans[u]!=0)return;
			ans[u] = c;
			--v;
			for (auto x:adj[u]){
				if (x == parent[u])continue;
				mark(x,c);
			}
		};
		if (sz[order[index]] >=brr[0] && n - sz[order[index]] >=brr[1]){
			v = brr[0];
			mark(order[index],ord[0] + 1);
			v = brr[1];
			mark(0,ord[1] + 1);
		}
		else if (sz[order[index]]>=brr[1] && n - sz[order[index]] >=brr[0]){
			v = brr[1];
			mark(order[index],ord[1] + 1);
			v = brr[0];
			mark(0,ord[0] + 1);
		}
		for (int i = 0;i<n;++i){
			if (ans[i] == 0)ans[i] = ord[2] + 1;
		}
		return ans;
	}
	if (n <=2500 && m <=5000){
		bool found = false;
		for (int i = 0;i<n;++i){
			DSU st;
			st.build(n);
			for (int j = 0;j<m;++j){
				if (p[j] == i || q[j] == i)continue;
				st.unionset(p[j],q[j]);
			}
			vector<bool>visited(n,false);
			vector<pair<int,int>>got;
			for (int j = 0;j<n;++j){
				if (i == j)continue;
				int temp =st.findsets(j);
				if (!visited[temp]){
					visited[temp] = true;
					got.push_back({st.sz[temp],temp});
				}
			}
			sort(got.rbegin(),got.rend());
			if ((int)got.size() > 1){
				if (got[0].first >=brr[1] && got[1].first + 1>=brr[0]){
					for (int j = 0;j<n;++j){
						if (st.findsets(j) == got[0].second && brr[1]){
							brr[1]--;
							ans[j] = ord[1] + 1;
						}
						else if (st.findsets(j) == got[1].second && brr[0]){
							brr[0]--;
							ans[j] = ord[0] + 1;
						}
						else ans[j] = ord[2] + 1;
					}
					if (brr[0]){
						ans[i] = ord[0] + 1;
					}
					found = true;
				}
				else if (got[0].first + 1>=brr[1] && got[1].first>=brr[0]){
					for (int j = 0;j<n;++j){
						if (st.findsets(j) == got[0].second && brr[1]){
							brr[1]--;
							ans[j] = ord[1] + 1;
						}
						else if (st.findsets(j) == got[1].second && brr[0]){
							brr[0]--;
							ans[j] = ord[0] + 1;
						}
						else ans[j] = ord[2] + 1;
					}
					if (brr[1]){
						ans[i] = ord[1] + 1;
					}
					found = true;
				}
			}
			else if ((int)got.size() == 1){
				if (got[0].first>=brr[1] && brr[0]<=1){
					for (int j = 0;j<n;++j){
						if (st.findsets(j) == got[0].second && brr[1]){
							brr[1]--;
							ans[j] = ord[1] + 1;
						}
						else ans[j] = ord[2] + 1;
					}
					if (brr[0]){
						ans[i] = ord[0] + 1;
					}
					found = true;
				}
			}
			if (found){
				break;
			}
		}
		if (!found)return ans;
		for (int i = 0;i<n;++i){
			if (ans[i] == 0)ans[i] = ord[2] + 1;
		}	
		return ans;
	}
	
	vector<int>dfs_low(n,0),dfs_initial(n,0),parent(n,-1);
	int time = 0;
	int rootnodes = 0;
	for (int i = 0;i<n;++i){
		function<void(int)>dfs = [&](int u){
			dfs_initial[u] = ++time;
			dfs_low[u] = ++time;
			for (auto x:adj[u]){
				if (!dfs_initial[x]){
					parent[x] = u;
					dfs(x);
					if (u == 0){
						rootnodes++;
					}
					if (dfs_low[x] >= dfs_initial[u]){
						articulation_point[x] = true;
					}
					dfs_low[u] = min(dfs_low[u],dfs_low[x]);
				}
				else if (x!=parent[u]){
					dfs_low[u] = min(dfs_low[u],dfs_initial[x]);
				}
			}	
		};
		rootnodes = 0;
		if (!dfs_initial[i])dfs(i);
		if (rootnodes > 1){
			articulation_point[i] = true;
		}
	}
	int counts = 0;
	vector<bool>visited(n,false);
	vector<vector<int>>answer;
	function<void(int)> dfs2 = [&](int u){
		visited[u] = true;
		counts++;
		for (auto x:adj[u]){
			if (!visited[x])dfs2(x);
		}
	};
	int index = -1;
	for (int i = 0;i<n;++i){
		if (articulation_point[i]){
			vector<int>pos;
			for (int j = 0;j<n;++j)visited[j] = false;
			vector<pair<int,int>>temp_edges;
			for (auto x:adj[i]){
				adj[x].erase(i);
				temp_edges.push_back({x,i});
			}
			for (auto x:adj[i]){
				if (!visited[x]){
					counts = 0;
					dfs2(x);
					pos.push_back(counts);
				}
			}
			sort(pos.rbegin(),pos.rend());
			if ((int)pos.size() >  1){
				if (pos[0] >= brr[1]){
					if (pos[1] + 1 >=brr[0]){
						index = i;
					}
				}
				else if (pos[0] + 1>=brr[1]){
					if (pos[1] >=brr[0]){
						index = i;
					}
				}
			}
			else if ((int)pos.size() > 0){
				if (pos[0] >=brr[1]){
					if (brr[0]<=1){
						index = i;
					}
				}
			}
			for (auto x:temp_edges){
				adj[x.first].insert(x.second);
			}
		}
		if (index!=-1)break;
	}
	if (index == -1)return ans;
	for (auto x:adj[index]){
		adj[x].erase(index);
	}
	function<void(int)> dfs3 = [&](int u){
		visited[u] = true;
		counts++;
		answer.back().push_back(u);
		for (auto x:adj[u]){
			if (!visited[x])dfs3(x);
		}
	};
	vector<int>pos;
	for (int j = 0;j<n;++j)visited[j] = false;
	for (auto x:adj[index]){
		if (!visited[x]){
			counts = 0;
			answer.emplace_back();
			dfs3(x);
			pos.push_back(counts);
		}
	}
	vector<int>order((int)pos.size());
	iota(order.begin(),order.end(),0);
	sort(order.begin(),order.end(),[&](int i,int j){
		return pos[i] > pos[j];
	});
	if (pos.size() > 1){
		if (pos[order[0]] >= brr[1]){
			if (pos[order[1]] + 1 >=brr[0]){
				for (auto x:answer[order[0]]){
					if (!brr[1])break;
					brr[1]--;
					ans[x] = ord[1] + 1;
				}
				for (auto x:answer[order[1]]){
					if (brr[0] <=1)break;
					--brr[0];
					ans[x] = ord[0] + 1;
				}
				if (brr[0])
					ans[index] = ord[0] + 1;
			}
		}
		else if (pos[order[0]] + 1>=brr[1]){
			if (pos[order[1]] >=brr[0]){
				for (auto x:answer[order[0]]){
					if (brr[1]<=1)break;
					--brr[1];
					ans[x] = ord[1] + 1;
				}
				for (auto x:answer[order[1]]){
					if (!brr[0])break;
					--brr[0];
					ans[x] = ord[0] + 1;
				}
				if (brr[1])
					ans[index] = ord[1] + 1;
			}
		}
	}
	else{
		if (pos[order[0]] >=brr[1]){
			if (brr[0]<=1){
				for (auto x:answer[order[0]]){
					if (!brr[1])break;
					--brr[1];
					ans[x] = ord[1] + 1;
				}
				if (brr[0] == 1){
					ans[index] = ord[0] + 1;
				}
			}
		}
	}
	for (int i = 0;i<n;++i)if(ans[i]==0)ans[i] = ord[2] + 1;
	return ans;
}	

• Subtask 1: 0 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36