Submission #1049231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049231		aykhn	Split the Attractions (IOI19_split)	C++17	100 / 100	65 ms	26356 KiB

split

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

using namespace std;

const int MXN = 1e5 + 5;

int n, A, B, C;
array<int, 2> col[3];
vector<int> adj[MXN], g[MXN], g1[MXN];
int comp[MXN];
int used[MXN], sz[MXN];
vector<int> ans;

void build(int a)
{
	used[a] = 1;
	for (int &v : adj[a])
	{
		if (used[v]) continue;
		g[a].push_back(v);
		g[v].push_back(a);
		build(v);
	}
}
void getsz(int a, int p, int cc)
{
	comp[a] = cc;
	sz[a] = 1;
	for (int &v : g[a])
	{
		if (v == p) continue;
		getsz(v, a, cc);
		sz[a] += sz[v];
	}
}
int findcent(int a, int p)
{
	for (int &v : g[a])
	{
		if (v == p) continue;
		if (sz[v] * 2 >= n) return findcent(v, a); 
	}
	return a;
}
void color(int a, int del, int p, int t)
{
	if (!col[t][0]) return;
	ans[a] = col[t][1];
	col[t][0]--;
	for (int &v : g[a])
	{
		if (v == del || v == p || ans[v]) continue;
		color(v, del, a, t);
	}
}
vector<int> o;
void dfs(int a)
{
	o.push_back(a);
	used[a] = 1;
	for (int &v : g1[a])
	{
		if (used[v]) continue;
		dfs(v);
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) 
{
	ans.assign(N, 0);
	col[0] = {a, 1}, col[1] = {b, 2}, col[2] = {c, 3};
	sort(col, col + 3);
	n = N, A = a, B = b, C = c;
	for (int i = 0; i < p.size(); i++)
	{
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	build(0);
	getsz(0, 0, 0);
	int r = findcent(0, 0);
	for (int &v : g[r])
	{
		getsz(v, r, v);
		if (sz[v] >= col[0][0]) 
		{
			color(v, r, r, 0);
			color(r, v, v, 1);
			for (int &i : ans) i = (!i ? col[2][1] : i);
			return ans;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (i == r) continue;
		for (int &j : adj[i])
		{
			if (j == r) continue;
			g1[comp[i]].push_back(comp[j]);
		}
	}
	fill(used, used + n, 0);
	for (int i = 0; i < n; i++)
	{
		if (i == r || comp[i] != i || used[i]) continue;
		o.clear();
		dfs(i);
		int s = 0;
		for (int i = 0; i < o.size(); i++) s += sz[o[i]];
		if (s < col[0][0]) continue;
		s = 0;
		int tmp = col[0][0];
		for (int i = 0; i < o.size(); i++)
		{
			if (s >= tmp) break;
			s += sz[o[i]];
			color(o[i], r, r, 0);
		}
		color(r, -1, r, 1);
		for (int &i : ans) i = (!i ? col[2][1] : i);
		return ans;
	}
	return vector<int> (n, 0);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
split.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (int i = 0; i < o.size(); i++) s += sz[o[i]];
      |                   ~~^~~~~~~~~~
split.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = 0; i < o.size(); i++)
      |                   ~~^~~~~~~~~~

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