Submission #772844

#	Time	Username	Problem	Language	Result	Execution time	Memory
772844		Abrar_Al_Samit	Split the Attractions (IOI19_split)	C++17	22 / 100	434 ms	1048576 KiB

split

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

const int nax = 1e5 + 3;

//subtask 1&3

vector<int>g[nax];
int m, n;
int sub[nax];
bool taken[nax];


int dfs(int v, int p) {
	sub[v] = 1;
	for(int u : g[v]) if(u!=p) {
		sub[v] += dfs(u, v);
	}
	return sub[v];
}
int get_centroid(int v, int p) {
	for(int u : g[v]) if(u!=p) {
		if(sub[u]*2>n) {
			return get_centroid(u, v);
		}
	}
	return v;
}
vector<int> find_split(int N, int A, int B, int C, 
	vector<int> p, vector<int> q) {
	n = N;

	vector<int>sz = {A, B, C}, ord = {0, 1, 2};	
	sort(ord.begin(), ord.end(), [&] (int i, int j) {
		return sz[i] < sz[j];
	});

	m = p.size();
	for(int i=0; i<m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}

	dfs(0, 0);

	int ct = get_centroid(0, 0);

	dfs(ct, ct);

	int bc = -1;
	for(int u : g[ct]) {
		if(sub[u]>=sz[ord[0]]) {
			bc = u;
			break;
		}
	}
	if(bc==-1) {
		return vector<int>(n, 0);
	}

	taken[ct] = 1;

	vector<int>g1;
	queue<int>qu;
	qu.push(bc);

	while(g1.size()<sz[ord[0]]) {
		int v = qu.front();
		qu.pop();

		if(taken[v]) continue;
		taken[v] = 1;
		g1.push_back(v);

		for(int u : g[v]) if(!taken[u]) {
			qu.push(u);
		}
	}

	taken[ct] = 0;
	while(!qu.empty()) qu.pop();
	qu.push(ct);
	vector<int>g2;
	while(g2.size()<sz[ord[1]]) {
		int v = qu.front();
		qu.pop();

		if(taken[v]) continue;
		taken[v] = 1;
		g2.push_back(v);

		for(int u : g[v]) if(!taken[u]) {
			qu.push(u);
		}
	}

	vector<int>res(n, 0);
	for(int x : g1) {
		res[x] = ord[0]+1;
	}
	for(int x : g2) {
		res[x] = ord[1]+1;
	}
	for(int i=0; i<n; ++i) if(res[i]==0) {
		res[i] = ord[2]+1;
	}
	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:68:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   68 |  while(g1.size()<sz[ord[0]]) {
split.cpp:85:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   85 |  while(g2.size()<sz[ord[1]]) {

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