oj.uz

Submission #143728

# Submission time Handle Problem Language Result Execution time Memory
143728 2019-08-15T01:29:38 Z joseacaz Split the Attractions (IOI19_split) C++17
18 / 100
 164 ms 15884 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 = nodeA;
		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 7 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 8 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 116 ms 15736 KB ok, correct split
8 Correct 114 ms 14328 KB ok, correct split
9 Correct 127 ms 13932 KB ok, correct split
10 Correct 135 ms 15884 KB ok, correct split
11 Correct 132 ms 15140 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 5032 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 129 ms 12128 KB ok, correct split
5 Correct 119 ms 11400 KB ok, correct split
6 Correct 164 ms 15844 KB ok, correct split
7 Correct 136 ms 14200 KB ok, correct split
8 Correct 143 ms 12792 KB ok, correct split
9 Correct 113 ms 11256 KB ok, correct split
10 Correct 72 ms 12272 KB ok, correct split
11 Correct 75 ms 12212 KB ok, correct split
12 Correct 77 ms 12144 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 108 ms 11480 KB ok, correct split
3 Correct 40 ms 7544 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 119 ms 12892 KB ok, correct split
6 Correct 112 ms 12664 KB ok, correct split
7 Correct 112 ms 12780 KB ok, correct split
8 Correct 109 ms 13404 KB ok, correct split
9 Correct 116 ms 12636 KB ok, correct split
10 Incorrect 38 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 5112 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 7 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 8 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 116 ms 15736 KB ok, correct split
8 Correct 114 ms 14328 KB ok, correct split
9 Correct 127 ms 13932 KB ok, correct split
10 Correct 135 ms 15884 KB ok, correct split
11 Correct 132 ms 15140 KB ok, correct split
12 Correct 6 ms 4984 KB ok, correct split
13 Correct 6 ms 5032 KB ok, correct split
14 Correct 6 ms 4984 KB ok, correct split
15 Correct 129 ms 12128 KB ok, correct split
16 Correct 119 ms 11400 KB ok, correct split
17 Correct 164 ms 15844 KB ok, correct split
18 Correct 136 ms 14200 KB ok, correct split
19 Correct 143 ms 12792 KB ok, correct split
20 Correct 113 ms 11256 KB ok, correct split
21 Correct 72 ms 12272 KB ok, correct split
22 Correct 75 ms 12212 KB ok, correct split
23 Correct 77 ms 12144 KB ok, correct split
24 Correct 6 ms 4984 KB ok, correct split
25 Correct 108 ms 11480 KB ok, correct split
26 Correct 40 ms 7544 KB ok, correct split
27 Correct 6 ms 5112 KB ok, correct split
28 Correct 119 ms 12892 KB ok, correct split
29 Correct 112 ms 12664 KB ok, correct split
30 Correct 112 ms 12780 KB ok, correct split
31 Correct 109 ms 13404 KB ok, correct split
32 Correct 116 ms 12636 KB ok, correct split
33 Incorrect 38 ms 7544 KB invalid split: #1=61, #2=11111, #3=22161
34 Halted 0 ms 0 KB -