oj.uz

Submission #143729

# Submission time Handle Problem Language Result Execution time Memory
143729 2019-08-15T01:39:10 Z joseacaz Split the Attractions (IOI19_split) C++17
18 / 100
 170 ms 15972 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, vis[MAXN], vis2[MAXN], centroid;
vi Tree[MAXN], Graph[MAXN], ans, nodes2;
vector < pii > part ( 3, {0, 0} );
map<pii, int> MP;

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 && !vis[i] )
			paint ( i, node, color );
}

bool possible ( int node )
{
	if ( nodes )
		nodes -= sz[node];
	vis[node] = 1;
	
	for ( auto i : Graph[node] )
		if ( !vis[i] && possible ( i ) )
			return 1;
	return 0;
}

void paint2 ( int node, int color )
{
	if ( nodes > 0 )
	{
		paint ( node, centroid, color );
		vis[node] = 1;
	}
	
	vis2[node] = 1;
	for ( auto i : Graph[node] )
		if ( !vis2[i] )
			paint2 ( i, 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 );
	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;
		nodes2.push_back ( i );
	}
	
	if ( nodeA != -1 )
	{
		nodes = part[0].first;
		paint ( nodeA, centroid, part[0].second );
		vis[nodeA] = 1;
		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]) && !MP[{look(p[i]), look(q[i])}])
		{
			Graph[look(p[i])].push_back ( look(q[i]) );
			Graph[look(q[i])].push_back ( look(p[i]) );
			MP[{look(p[i]), look(q[i])}] = 1;
			MP[{look(q[i]), look(p[i])}] = 1;
		}
	}
	
	for ( auto i : nodes2 )
	{
		if ( vis[i] )
			continue;
		
		nodes = part[0].first;
		possible ( i );
		
		if ( nodes <= 0 )
		{
			for ( auto j : nodes2 )
				vis[j] = 0;
			nodes = part[0].first;
			paint2 ( i, part[0].second );
			nodes = part[1].first;
			paint ( centroid, -1, part[1].second );
			return ans;
		}
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 7 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 7 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 155 ms 15900 KB ok, correct split
8 Correct 142 ms 14328 KB ok, correct split
9 Correct 116 ms 14020 KB ok, correct split
10 Correct 170 ms 15964 KB ok, correct split
11 Correct 144 ms 15068 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 132 ms 12208 KB ok, correct split
5 Correct 104 ms 11356 KB ok, correct split
6 Correct 146 ms 15972 KB ok, correct split
7 Correct 114 ms 14328 KB ok, correct split
8 Correct 158 ms 12984 KB ok, correct split
9 Correct 119 ms 11384 KB ok, correct split
10 Correct 75 ms 12140 KB ok, correct split
11 Correct 75 ms 12284 KB ok, correct split
12 Correct 85 ms 12168 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 107 ms 11384 KB ok, correct split
3 Correct 41 ms 7672 KB ok, correct split
4 Correct 6 ms 4956 KB ok, correct split
5 Correct 105 ms 12792 KB ok, correct split
6 Correct 121 ms 12740 KB ok, correct split
7 Correct 111 ms 12676 KB ok, correct split
8 Correct 136 ms 13400 KB ok, correct split
9 Correct 123 ms 12664 KB ok, correct split
10 Incorrect 37 ms 7544 KB invalid split: #1=61, #2=11111, #3=22161
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Incorrect 6 ms 4984 KB invalid split: #1=1, #2=2, #3=3
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 7 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 7 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 155 ms 15900 KB ok, correct split
8 Correct 142 ms 14328 KB ok, correct split
9 Correct 116 ms 14020 KB ok, correct split
10 Correct 170 ms 15964 KB ok, correct split
11 Correct 144 ms 15068 KB ok, correct split
12 Correct 6 ms 4984 KB ok, correct split
13 Correct 6 ms 4984 KB ok, correct split
14 Correct 6 ms 4984 KB ok, correct split
15 Correct 132 ms 12208 KB ok, correct split
16 Correct 104 ms 11356 KB ok, correct split
17 Correct 146 ms 15972 KB ok, correct split
18 Correct 114 ms 14328 KB ok, correct split
19 Correct 158 ms 12984 KB ok, correct split
20 Correct 119 ms 11384 KB ok, correct split
21 Correct 75 ms 12140 KB ok, correct split
22 Correct 75 ms 12284 KB ok, correct split
23 Correct 85 ms 12168 KB ok, correct split
24 Correct 6 ms 4984 KB ok, correct split
25 Correct 107 ms 11384 KB ok, correct split
26 Correct 41 ms 7672 KB ok, correct split
27 Correct 6 ms 4956 KB ok, correct split
28 Correct 105 ms 12792 KB ok, correct split
29 Correct 121 ms 12740 KB ok, correct split
30 Correct 111 ms 12676 KB ok, correct split
31 Correct 136 ms 13400 KB ok, correct split
32 Correct 123 ms 12664 KB ok, correct split
33 Incorrect 37 ms 7544 KB invalid split: #1=61, #2=11111, #3=22161
34 Halted 0 ms 0 KB -