oj.uz

Submission #143721

# Submission time Handle Problem Language Result Execution time Memory
143721 2019-08-15T00:48:37 Z joseacaz Split the Attractions (IOI19_split) C++17
0 / 100
 6 ms 5036 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 100005;

int N, M, sz[MAXN], parent[MAXN], nodes, nodeA;
vi Tree[MAXN], Graph[MAXN], ans;
vector < pii > part ( 3, {0, 0} );

int pre ( int node, int p = -1 )
{
	sz[node] = 1;
	for ( auto i : Tree[node] )
		if ( i != p )
			sz[node] += pre ( i, node );
	return sz[node];
}

int find_centroid ( int node, int p = -1 )
{
	for ( auto i : Tree[node] )
		if ( i != p && sz[i] > sz[0] / 2 )
			return find_centroid ( i, node );
	return node;
}

int look ( int node )
{
	if ( node == parent[node] )
		return node;
	return parent[node] = look ( parent[node] );
}

void join ( int nodeA, int nodeB )
{
	parent[look(nodeB)] = look(nodeA);
}

void dfs ( int root, int node, int p = -1 )
{
	join ( root, node );
	for ( auto i : Tree[node] )
		if ( i != p )
			dfs ( root, i, node );
}

void paint ( int node, int p, int color )
{
	if ( nodes )
		ans[node] = color, nodes--;
	else
		ans[node] = part[2].second;
	
	for ( auto i : Tree[node] )
		if ( i != p && i != nodeA )
			paint ( i, node, color );
}

vi find_split ( int _n, int a, int b, int c, vi p, vi q )
{
	part[0] = {a, 1};
	part[1] = {b, 2};
	part[2] = {c, 3};
	sort ( part.begin(), part.end() );
	N = _n;
	M = p.size();

	ans.resize ( N );
	for ( int i = 0; i < N; i++ )
		parent[i] = i, ans[i] = 0;
	for ( int i = 0; i < M; i++ )
	{
		if ( look ( p[i] ) != look ( q[i] ) )
		{
			join ( p[i], q[i] );
			Tree[p[i]].push_back ( q[i] );
			Tree[q[i]].push_back ( p[i] );
		}
	}
	
	pre ( 0 );
	int centroid = find_centroid ( 0 );
	pre ( centroid );
	for ( int i = 0; i < N; i++ )
		parent[i] = i;
	
	nodeA = -1;
	for ( auto i : Tree[centroid] )
	{
		dfs ( i, i, centroid );
		if ( sz[i] >= part[0].first )
			nodeA = i;
	}
	
	cout << nodeA << " " << sz[nodeA] << "\n";
	if ( nodeA != -1 )
	{
		nodes = part[0].first;
		paint ( nodeA, centroid, part[0].second );
		nodes = part[1].first;
		paint ( centroid, -1, part[1].second );
	}
	return ans;

	/*for ( int i = 0; i < M; i++ )
	{
		if ( look(p[i]) != look(q[i]) )
		{
			join ( p[i], q[i] );
			Graph[look(p[i])].push_back ( look(q[i]) );
			Graph[look(q[i])].push_back ( look(p[i]) );
		}
	}*/
	
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5036 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4956 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB secret mismatch
2 Halted 0 ms 0 KB -