Submission #197842

#	Time	Username	Problem	Language	Result	Execution time	Memory
197842		arnold518	Split the Attractions (IOI19_split)	C++14	100 / 100	246 ms	25952 KiB

split

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, ans[MAXN+10];
pii A[4];
vector<int> adj[MAXN+10], adj2[MAXN+10], adj3[MAXN+10];
	
int sz[MAXN+10], id[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		getsz(nxt, now);
		sz[now]+=sz[nxt];
	}
}

int getcen(int now, int bef, int S)
{
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		if(sz[nxt]>S/2) return getcen(nxt, now, S);
	}
	return now;
}

void color(int now, int bef, int col, int &k)
{
	if(k<=0) return;
	ans[now]=col; k--;
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		if(ans[nxt]) continue;
		color(nxt, now, col, k);
	}
}

void color2(int now, int bef, int root)
{
	id[now]=root;
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		color2(nxt, now, root);
	}
}

bool vis[MAXN+10];
void dfs(int now)
{
	vis[now]=true;
	for(int nxt : adj[now])
	{
		if(vis[nxt]) continue;
		adj2[now].push_back(nxt);
		adj2[nxt].push_back(now);
		dfs(nxt);
	}
}

vector<int> V;
void dfs2(int now, int &k)
{
	vis[now]=true;
	k+=sz[now]; V.push_back(now);
	if(k>=A[1].first) return;
	for(int nxt : adj3[now])
	{
		if(vis[nxt]) continue;
		dfs2(nxt, k);
	}
}

void solve()
{
	int i, j;

	memset(vis, 0, sizeof(vis));
	dfs(1);
	getsz(1, 1);
	int cen=getcen(1, 1, N);
	getsz(cen, cen);

	for(int now : adj2[cen])
	{
		color2(now, cen, now);
		if(A[1].first<=sz[now])
		{
			int t=A[1].first;
			color(now, cen, A[1].second, t);
			t=A[2].first;
			color(cen, now, A[2].second, t);
			for(i=1; i<=N; i++) if(ans[i]==0) ans[i]=A[3].second;
			return;
		}
	}

	for(i=1; i<=N; i++)
	{
		int now=i;
		if(now==cen) continue;
		for(int nxt : adj[now])
		{
			if(nxt==cen) continue;
			if(id[now]==id[nxt]) continue;
			adj3[id[now]].push_back(id[nxt]);
		}
	}

	memset(vis, 0, sizeof(vis));
	for(int now : adj2[cen])
	{
		if(vis[now]) continue;
		int t=0;
		dfs2(now, t);
		if(t<A[1].first) continue;

		t=A[1].first;
		for(auto it : V) color(it, cen, A[1].second, t);
		color(cen, cen, A[2].second, A[2].first);
		for(i=1; i<=N; i++) if(ans[i]==0) ans[i]=A[3].second;
		return;
	}
}

vector<int> find_split(int _N, int _A, int _B, int _C, vector<int> _P, vector<int> _Q)
{
	int i, j;
	N=_N; A[1]=pii(_A, 1); A[2]=pii(_B, 2); A[3]=pii(_C, 3);
	for(i=0; i<_P.size(); i++)
	{
		int u=_P[i]+1, v=_Q[i]+1;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	sort(A+1, A+4);

	solve();

	vector<int> _ans(N);
	for(i=1; i<=N; i++) _ans[i-1]=ans[i];
	return _ans;
}

Compilation message (stderr)

split.cpp: In function 'void solve()':
split.cpp:88:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:142:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<_P.size(); i++)
           ~^~~~~~~~~~
split.cpp:140:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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