Submission #601692

#	Time	Username	Problem	Language	Result	Execution time	Memory
601692		Apiram	Split the Attractions (IOI19_split)	C++14	11 / 100	2067 ms	30380 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

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>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;
	}
	vector<int>ans(n,0);
	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;
				}
				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;
				}
				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: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36