Submission #143951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
143951	2019-08-15T13:32:50 Z	joseacaz	Split the Attractions (IOI19_split)	C++17	40 / 100	154 ms	17312 KB

split

#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], total[MAXN], centroid, component[MAXN], sum;
vi MST[MAXN], Graph[MAXN], ans, TP;
vector<pii> part ( 3, {0, 0} );

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

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

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

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

void paint ( int node, int p, int color )
{
	if ( ans[node] )
		return;

	if ( part[color].first )
	{
		part[color].first--;
		ans[node] = part[color].second;
	}
	else
		ans[node] = part[2].second;
	
	for ( auto i : MST[node] )
		if ( i != p )
			paint ( i, node, color );
}

void compress ( int root, int node, int p )
{
	component[node] = root;
	for ( auto i : MST[node] )
		if ( i != p )
			compress ( root, i, node );
}

void check ( int node, int p = -1 )
{
	sum += sz[node];
	TP.push_back ( node );
	if ( sum >= part[0].first )
		return;
	
	for ( auto i : Graph[node] )
		if ( i != p )
			check ( i, node );
}

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;
	for ( int i = 0; i < M; i++ )
	{
		if ( look ( p[i] ) != look ( q[i] ) )
		{
			MST[p[i]].push_back ( q[i] );
			MST[q[i]].push_back ( p[i] );
			join ( p[i], q[i] );
		}
	}
	
	pre ( 0 );
	centroid = find_centroid ( 0 );
	pre ( centroid );
	
	component[centroid] = centroid;
	for ( auto i : MST[centroid] )
	{
		if ( sz[i] >= part[0].first )
		{
			paint ( i, centroid, 0 );
			paint ( centroid, -1, 1 );
			return ans;
		}
		
		compress ( i, i, centroid );
	}
	
	for ( int i = 0; i < N; i++ )
		parent[i] = i;
	for ( int i = 0; i < M; i++ )
	{
		if ( p[i] == centroid or q[i] == centroid )
			continue;

		if ( look ( component[p[i]] ) != look ( component[q[i]] ) )
		{
			join ( component[p[i]], component[q[i]] );
			Graph[component[p[i]]].push_back ( component[q[i]] );
			Graph[component[q[i]]].push_back ( component[p[i]] );
		}
	}
	
	for ( auto i : MST[centroid] )
	{
		sum = 0;
		check ( i );
		if ( sum >= part[0].first )
		{
			for ( auto j : TP )
				paint ( j, centroid, 0 );
			paint ( centroid, -1, 1 );
			return ans;
		}
	}
	for ( auto &i : ans )
		i = 0;
	return ans;
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 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	6 ms	4984 KB	ok, correct split
5	Correct	6 ms	5112 KB	ok, correct split
6	Correct	7 ms	5112 KB	ok, correct split
7	Correct	117 ms	17272 KB	ok, correct split
8	Correct	132 ms	15484 KB	ok, correct split
9	Correct	126 ms	14840 KB	ok, correct split
10	Correct	145 ms	17312 KB	ok, correct split
11	Correct	137 ms	16376 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	128 ms	12156 KB	ok, correct split
5	Correct	100 ms	11384 KB	ok, correct split
6	Correct	145 ms	17272 KB	ok, correct split
7	Correct	132 ms	15352 KB	ok, correct split
8	Correct	154 ms	12796 KB	ok, correct split
9	Correct	124 ms	11356 KB	ok, correct split
10	Correct	69 ms	11628 KB	ok, correct split
11	Correct	70 ms	11644 KB	ok, correct split
12	Correct	72 ms	11740 KB	ok, correct split

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4984 KB	ok, correct split
2	Correct	151 ms	11768 KB	ok, correct split
3	Correct	44 ms	7672 KB	ok, correct split
4	Correct	7 ms	4984 KB	ok, correct split
5	Correct	153 ms	13800 KB	ok, correct split
6	Correct	117 ms	13560 KB	ok, correct split
7	Correct	139 ms	13736 KB	ok, correct split
8	Correct	144 ms	14456 KB	ok, correct split
9	Correct	144 ms	13588 KB	ok, correct split
10	Correct	33 ms	7288 KB	ok, no valid answer
11	Correct	48 ms	8440 KB	ok, no valid answer
12	Correct	90 ms	12532 KB	ok, no valid answer
13	Correct	97 ms	11896 KB	ok, no valid answer
14	Correct	79 ms	12656 KB	ok, no valid answer

Subtask #4
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4992 KB	ok, correct split
2	Correct	6 ms	4984 KB	ok, no valid answer
3	Correct	6 ms	4984 KB	ok, correct split
4	Correct	6 ms	4984 KB	ok, correct split
5	Correct	6 ms	4984 KB	ok, correct split
6	Correct	6 ms	4984 KB	ok, correct split
7	Correct	6 ms	4984 KB	ok, correct split
8	Correct	7 ms	4956 KB	ok, correct split
9	Correct	8 ms	5240 KB	ok, correct split
10	Correct	8 ms	5240 KB	ok, correct split
11	Correct	6 ms	5112 KB	ok, correct split
12	Incorrect	9 ms	5240 KB	2 components are not connected
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 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	6 ms	4984 KB	ok, correct split
5	Correct	6 ms	5112 KB	ok, correct split
6	Correct	7 ms	5112 KB	ok, correct split
7	Correct	117 ms	17272 KB	ok, correct split
8	Correct	132 ms	15484 KB	ok, correct split
9	Correct	126 ms	14840 KB	ok, correct split
10	Correct	145 ms	17312 KB	ok, correct split
11	Correct	137 ms	16376 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	128 ms	12156 KB	ok, correct split
16	Correct	100 ms	11384 KB	ok, correct split
17	Correct	145 ms	17272 KB	ok, correct split
18	Correct	132 ms	15352 KB	ok, correct split
19	Correct	154 ms	12796 KB	ok, correct split
20	Correct	124 ms	11356 KB	ok, correct split
21	Correct	69 ms	11628 KB	ok, correct split
22	Correct	70 ms	11644 KB	ok, correct split
23	Correct	72 ms	11740 KB	ok, correct split
24	Correct	6 ms	4984 KB	ok, correct split
25	Correct	151 ms	11768 KB	ok, correct split
26	Correct	44 ms	7672 KB	ok, correct split
27	Correct	7 ms	4984 KB	ok, correct split
28	Correct	153 ms	13800 KB	ok, correct split
29	Correct	117 ms	13560 KB	ok, correct split
30	Correct	139 ms	13736 KB	ok, correct split
31	Correct	144 ms	14456 KB	ok, correct split
32	Correct	144 ms	13588 KB	ok, correct split
33	Correct	33 ms	7288 KB	ok, no valid answer
34	Correct	48 ms	8440 KB	ok, no valid answer
35	Correct	90 ms	12532 KB	ok, no valid answer
36	Correct	97 ms	11896 KB	ok, no valid answer
37	Correct	79 ms	12656 KB	ok, no valid answer
38	Correct	6 ms	4992 KB	ok, correct split
39	Correct	6 ms	4984 KB	ok, no valid answer
40	Correct	6 ms	4984 KB	ok, correct split
41	Correct	6 ms	4984 KB	ok, correct split
42	Correct	6 ms	4984 KB	ok, correct split
43	Correct	6 ms	4984 KB	ok, correct split
44	Correct	6 ms	4984 KB	ok, correct split
45	Correct	7 ms	4956 KB	ok, correct split
46	Correct	8 ms	5240 KB	ok, correct split
47	Correct	8 ms	5240 KB	ok, correct split
48	Correct	6 ms	5112 KB	ok, correct split
49	Incorrect	9 ms	5240 KB	2 components are not connected
50	Halted	0 ms	0 KB	-

Submission #143951

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 11.0 / 11.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 24.0

Subtask #5 0 / 36.0

Subtask #1
7.0 / 7.0

Subtask #2
11.0 / 11.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 24.0

Subtask #5
0 / 36.0