Submission #297664

#	Time	Username	Problem	Language	Result	Execution time	Memory
297664		Saboon	Split the Attractions (IOI19_split)	C++17	18 / 100	2051 ms	17788 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int A = 1, B = 2, C = 3;
int n, a, b, c, nA, nB, nC;
vector<int> g[maxn], res;
int sz[maxn], h[maxn];
bool visited[maxn];

int dfs3(int v, int col){
	visited[v] = 1;
	int Tmp = 0;
	for (auto u : g[v])
		if (!visited[u] and res[v] == res[u])
			Tmp += dfs3(u, col-Tmp);
	col -= Tmp;
	if (col > 0){
		nC ++, Tmp++;
		if (res[v] == A)
			nA --;
		else
			nB --;
		res[v] = C;
	}
	return Tmp;
}

void dfs2(int v, int col){
	res[v] = col;
	for (auto u : g[v])
		if (h[u] == h[v]+1)
			dfs2(u, col);
}

bool dfs(int v){
	visited[v] = 1;
	sz[v] = 1;
	for (auto u : g[v]){
		if (!visited[u]){
			h[u] = h[v]+1;
			if (dfs(u))
				return true;
			sz[v] += sz[u];
		}
	}
	if (sz[v] >= a and sz[v] <= n-b){
		for (int i = 0; i < n; i++)
			res[i] = B;
		nA = sz[v], nB = n-sz[v];
		dfs2(v, A);
		return true;
	}
	if (sz[v] >= b and sz[v] <= n-a){
		for (int i = 0; i < n; i++)
			res[i] = A;
		nB = sz[v], nA = n-sz[v];
		dfs2(v,B);
		return true;
	}
	return false;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	if (a > b)
		swap(a,b), swap(A,B);
	if (c > b)
		swap(c,b), swap(B,C);
	if (a > b)
		swap(a,b), swap(A,B);
	::n = n, ::a = a, ::b = b, ::c = c;
	for (int i = 0; i < p.size(); i++)
		g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
	res.resize(n);
	for (int i = 0; i < n; i++){
		memset(visited, 0, sizeof visited);
		h[i] = 0;
		if (dfs(i))
			break;
		if (i == n-1)
			return res;
	}
	memset(visited, 0, sizeof visited);
	for (int i = 0; i < n; i++){
		if (res[i] == A and nA > a)
			dfs3(i, nA-a);
		if (res[i] == B and nB > b)
			dfs3(i, nB-b);
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  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