Submission #197819

#	Time	Username	Problem	Language	Result	Execution time	Memory
197819		arnold518	Split the Attractions (IOI19_split)	C++14	22 / 100	910 ms	1048580 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];
	
int sz[MAXN+10];

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

void dfs(int now, int bef)
{
	int i, j;

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

	if(sz[now]>=A[1].first && N-sz[now]>=A[2].first)
	{
		for(i=1; i<=N; i++) ans[i]=A[3].second;
		int t=A[1].first;
		color(now, bef, A[1].second, t);
		t=A[2].first;
		color(bef, now, A[2].second, t);
	}
	else if(sz[now]>=A[2].first && N-sz[now]>=A[1].first)
	{
		for(i=1; i<=N; i++) ans[i]=A[3].second;
		int t=A[2].first;
		color(now, bef, A[2].second, t);
		t=A[1].first;
		color(bef, now, A[1].second, t);
	}
}

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);

	dfs(1, 1);

	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 dfs(int, int)':
split.cpp:30: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:62:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<_P.size(); i++)
           ~^~~~~~~~~~
split.cpp:60:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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