Submission #1010265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010265		ttamx	Split the Attractions (IOI19_split)	C++17	18 / 100	55 ms	18256 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n;
vector<int> adj[N];
int disc[N],low[N],sz[N];
int timer=0;
bool vis[N];

void dfs(int u,int p=-1){
	disc[u]=low[u]=++timer;
	sz[u]=1;
	for(auto v:adj[u]){
		if(!disc[v]){
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			sz[u]+=sz[v];
		}else if(v!=p){
			low[u]=min(low[u],disc[v]);
		}
	}
}

void dfs2(int u,int cnt,vector<int> &a){
	if(vis[u]||a.size()>=cnt)return;
	vis[u]=true;
	a.emplace_back(u);
	for(auto v:adj[u])dfs2(v,cnt,a);
}

vector<int> find_split(int _n,int a,int b,int c,vector<int> p,vector<int> q){
	n=_n;
	for(int i=0;i<p.size();i++){
		int u=p[i],v=q[i];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	dfs(0);
	pair<int,int> d[3]={{a,1},{b,2},{c,3}};
	sort(d,d+3);
	a=d[0].first,b=d[1].first;
	for(int u=0;u<n;u++){
		bool ok=sz[u]>=a;
		for(auto v:adj[u])if(disc[v]>disc[u])ok&=sz[v]<a;
		if(!ok)continue;
		vector<int> del;
		int cur=sz[u];
		for(auto v:adj[u])if(disc[v]>disc[u]&&low[v]<disc[u]&&cur-sz[v]>=a){
			cur-=sz[v];
			del.emplace_back(v);
		}
		if(n-cur<a)continue;
		vector<int> sa,sb;
		for(auto x:del)vis[x]=true;
		if(cur<n-cur)dfs2(u,a,sa);
		else dfs2(u,b,sb);
		for(auto x:del)vis[x]=false;;
		if(cur<n-cur)dfs2(0,b,sb);
		else dfs2(0,a,sa);
		vector<int> ans(n,d[2].second);
		for(auto x:sa)ans[x]=d[0].second;
		for(auto x:sb)ans[x]=d[1].second;
		return ans;
	}
	return vector<int>(n);
}

Compilation message (stderr)

split.cpp: In function 'void dfs2(int, int, std::vector<int>&)':
split.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  if(vis[u]||a.size()>=cnt)return;
      |             ~~~~~~~~^~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~

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