Submission #1151686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151686		Pacybwoah	Split the Attractions (IOI19_split)	C++20	29 / 100	588 ms	1114112 KiB

split

#include "split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
namespace{
	vector<int> ord;
	vector<int> sz, pa;
	vector<vector<int>> graph;
	void dfs(int node, int parent){
		sz[node] = 1;
		pa[node] = parent;
		ord.push_back(node);
		for(auto &x: graph[node]){
			if(x == parent) continue;
			dfs(x, node);
			sz[node] += sz[x];
		}
	}
	void dfs_ban(int node, int parent, int ban){
		ord.push_back(node);
		for(auto &x: graph[node]){
			if(x == parent || x == ban) continue;
			dfs_ban(x, node, ban);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> ans(n);
	sz.resize(n);
	graph.resize(n);
	pa.resize(n);
	for(int i = 0; i < n - 1; i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}
	dfs(0, 0);
	if(a == 1){
		for(int i = 0; i < b; i++) ans[ord[i]] = 2;
		for(int i = b; i < b + c; i++) ans[ord[i]] = 3;
		ans[ord[n - 1]] = 1;
		return ans;
	}
	int na = 1, nb = 2, nc = 3;
	if(a > b){
		swap(a, b);
		swap(na, nb);
	}
	if(b > c){
		swap(b, c);
		swap(nb, nc);
	}
	if(a > b){
		swap(a, b);
		swap(na, nb);
	}
	vector<int> old = ord, pos(n);
	for(int i = 0; i < n; i++) pos[ord[i]] = i;
	vector<int>().swap(ord);
	for(int i = 0; i < n; i++){
		if(sz[i] >= a && n - sz[i] >= b){
			dfs_ban(pa[i], pa[i], i);
			for(int j = pos[i]; j < pos[i] + a; j++) ans[old[j]] = na;
			for(int j = 0; j < b; j++) ans[ord[j]] = nb;
			for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
			return ans;
		}
		if(sz[i] >= b && n - sz[i] >= a){
			dfs_ban(pa[i], pa[i], i);
			for(int j = pos[i]; j < pos[i] + b; j++) ans[old[j]] = nb;
			for(int j = 0; j < a; j++) ans[ord[j]] = na;
			for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
			return ans;
		}
	}
	return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run split.cpp grader.cpp

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