Submission #724292

#	Time	Username	Problem	Language	Result	Execution time	Memory
724292		QwertyPi	Split the Attractions (IOI19_split)	C++14	0 / 100	6 ms	9684 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 11;
vector<int> G[N], sons[N];
bool vis[N]; int pa[N]; int sz[N];
void dfs(int v){
	vis[v] = true;
	for(auto i : G[v]){
		if(!vis[i]){
			dfs(i); pa[i] = v; sons[v].push_back(i);
		}
	}
}

void dfs2(int v){
	sz[v] = 1;
	for(auto i : sons[v]){
		dfs2(i); sz[v] += sz[i];
	}
}

vector<int> res;
int cur_sz = 0;
void bfs(int v, int par, int fil){
	if(cur_sz == 0) return;
	res[v] = fil; cur_sz--;
	for(auto i : sons[v]){
		bfs(i, v, fil);
	}
}
void bfs2(int v, int par, int fil){
	if(cur_sz == 0) return;
	res[v] = fil; cur_sz--;
	for(auto i : G[v]){
		if(i != par && !res[i]) bfs2(i, v, fil);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for(int i = 0; i < p.size(); i++){
		G[p[i]].push_back(q[i]);
		G[q[i]].push_back(p[i]);
	}
	int k = min(min(a, b), c);
	int v1 = 1, v2 = 2, v3 = 3;
	if(a > b) swap(a, b), swap(v1, v2);
	if(b > c) swap(b, c), swap(v2, v3);
	if(a > b) swap(a, b), swap(v1, v2);
	if(b > c) swap(b, c), swap(v2, v3);
	dfs(0);
	dfs2(0);
	res.resize(n);
	for(int rt = 0; rt < n; rt++){
		for(int j = 0; j < n; j++) sons[j].clear(); fill(sz, sz + n, 0);
		dfs(rt); dfs2(rt);
		for(int i = 0; i < n; i++){
			if(sz[i] >= k && sz[i] <= n - k){
				if(sz[i] <= n / 2){
					cur_sz = a; bfs(i, pa[i], v1);
					cur_sz = b; bfs2(pa[i], -1, v2);
					for(auto& i : res) if(i == 0) i = v3;
				}else{
					cur_sz = b; bfs(i, pa[i], v2);
					cur_sz = a; bfs2(pa[i], -1, v1);
					for(auto& i : res) if(i == 0) i = v3;
				}
				return res;
			}
		}
	}
	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:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0; i < p.size(); i++){
      |                 ~~^~~~~~~~~~
split.cpp:56:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |   for(int j = 0; j < n; j++) sons[j].clear(); fill(sz, sz + n, 0);
      |   ^~~
split.cpp:56:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |   for(int j = 0; j < n; j++) sons[j].clear(); fill(sz, sz + n, 0);
      |                                               ^~~~

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