Submission #987506

#	Time	Username	Problem	Language	Result	Execution time	Memory
987506		PagodePaiva	Split the Attractions (IOI19_split)	C++17	0 / 100	24 ms	7260 KiB

split

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

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

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

vector <int> aux[N];

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

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	for(int i = 0;i < p.size();i++){
		int x = p[i]+1, y = q[i]+1;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	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 st = 1;st <= n;st++){
		memset(mark, 0, sizeof mark);
		dfs(st, st);
		for(auto v : g[st]){
			if(sz[v] >= a and n-sz[v] >= b){
				solve(v, a, b);
				vector <int> ans;
				for(int i = 1;i <= n;i++) ans.push_back(res[i]);
				return ans;
			}
		}
	}
	vector <int> ans;
	for(int i = 0;i < n;i++) ans.push_back(0);
	return ans;
}

Compilation message (stderr)

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

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