Submission #986879

#	Time	Username	Problem	Language	Result	Execution time	Memory
986879		PagodePaiva	Split the Attractions (IOI19_split)	C++17	29 / 100	607 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n;
vector <int> g[N];
int sz[N];
int pai[N];
int res[N];
vector <int> tipos = {1, 2, 3};

void dfs(int v, int p){
	sz[v] = 1;
	pai[v] = p;
	for(auto x : g[v]){
		if(x == p) continue;
		dfs(x, v);
		sz[v] += sz[x];
	}
	return;
}

void dfs2(int v, int p, int& tam, int typ){
	if(tam == 0) return;
	res[v] = typ;
	tam--;
	for(auto x : g[v]){
		if(x == p) continue;
		dfs2(x, v, tam, typ);
	} 
	return;
}
void solve(int v, int a, int b){
	int p = pai[v];
	dfs2(v, pai[v], a, tipos[0]);
	dfs2(pai[v], v, b, tipos[1]);
	for(int i = 1;i <= n;i++){
		if(res[i] == 0) res[i] = tipos[2];
	}
	return;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	if(a > b) {
		swap(a, b);
		swap(tipos[0], tipos[1]);
	}
	if(a > c){
		swap(a, c);
		swap(tipos[0], tipos[2]);
	} 
	if(b > c) {
		swap(b, c);
		swap(tipos[1], tipos[2]);
	}
	for(int i = 1;i < n;i++){
		g[p[i-1]+1].push_back(q[i-1]+1);
		g[q[i-1]+1].push_back(p[i-1]+1);
	}
	dfs(1, 1);
	for(int i = 1;i <= n;i++){
		if(sz[i] >= a and n-sz[i] >= b){
			solve(i, a, b);
			vector <int> ans;
			for(int i = 1;i <= n;i++) ans.push_back(res[i]);
			return ans;
		}
		else if(sz[i] >= b and n-sz[i] >= a){
			swap(tipos[0], tipos[1]);
			solve(i, b, a);
			vector <int> ans;
			for(int i = 1;i <= n;i++) ans.push_back(res[i]);
			return ans;
		}
	}
	vector <int> ans;
	for(int i = 1;i <= n;i++) ans.push_back(0);
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void solve(int, int, int)':
split.cpp:35:6: warning: unused variable 'p' [-Wunused-variable]
   35 |  int p = pai[v];
      |      ^

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