#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;
}
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]) );
}
}*/
}
# |
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 |
9 ms |
4984 KB |
ok, correct split |
4 |
Correct |
6 ms |
5112 KB |
ok, correct split |
5 |
Correct |
6 ms |
4984 KB |
ok, correct split |
6 |
Correct |
6 ms |
4984 KB |
ok, correct split |
7 |
Correct |
134 ms |
15792 KB |
ok, correct split |
8 |
Correct |
124 ms |
14436 KB |
ok, correct split |
9 |
Correct |
133 ms |
14012 KB |
ok, correct split |
10 |
Correct |
148 ms |
15840 KB |
ok, correct split |
11 |
Correct |
133 ms |
15096 KB |
ok, correct split |
# |
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 |
142 ms |
12112 KB |
ok, correct split |
5 |
Correct |
113 ms |
11384 KB |
ok, correct split |
6 |
Correct |
167 ms |
15736 KB |
ok, correct split |
7 |
Correct |
134 ms |
14416 KB |
ok, correct split |
8 |
Correct |
153 ms |
12796 KB |
ok, correct split |
9 |
Correct |
122 ms |
11256 KB |
ok, correct split |
10 |
Correct |
74 ms |
11704 KB |
ok, correct split |
11 |
Correct |
74 ms |
11632 KB |
ok, correct split |
12 |
Correct |
77 ms |
11632 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
100 ms |
11360 KB |
ok, correct split |
3 |
Correct |
43 ms |
7672 KB |
ok, correct split |
4 |
Correct |
6 ms |
5112 KB |
ok, correct split |
5 |
Correct |
136 ms |
12920 KB |
ok, correct split |
6 |
Correct |
141 ms |
12664 KB |
ok, correct split |
7 |
Correct |
149 ms |
12664 KB |
ok, correct split |
8 |
Correct |
122 ms |
13528 KB |
ok, correct split |
9 |
Correct |
110 ms |
12640 KB |
ok, correct split |
10 |
Correct |
34 ms |
7288 KB |
ok, no valid answer |
11 |
Correct |
49 ms |
8184 KB |
ok, no valid answer |
12 |
Correct |
84 ms |
11552 KB |
ok, no valid answer |
13 |
Correct |
95 ms |
11384 KB |
ok, no valid answer |
14 |
Correct |
73 ms |
11632 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
7 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 |
4988 KB |
ok, correct split |
6 |
Correct |
6 ms |
4984 KB |
ok, correct split |
7 |
Correct |
6 ms |
4984 KB |
ok, correct split |
8 |
Correct |
6 ms |
4984 KB |
ok, correct split |
9 |
Correct |
9 ms |
5240 KB |
ok, correct split |
10 |
Correct |
9 ms |
5240 KB |
ok, correct split |
11 |
Correct |
6 ms |
5112 KB |
ok, correct split |
12 |
Incorrect |
9 ms |
5240 KB |
jury found a solution, contestant did not |
13 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
9 ms |
4984 KB |
ok, correct split |
4 |
Correct |
6 ms |
5112 KB |
ok, correct split |
5 |
Correct |
6 ms |
4984 KB |
ok, correct split |
6 |
Correct |
6 ms |
4984 KB |
ok, correct split |
7 |
Correct |
134 ms |
15792 KB |
ok, correct split |
8 |
Correct |
124 ms |
14436 KB |
ok, correct split |
9 |
Correct |
133 ms |
14012 KB |
ok, correct split |
10 |
Correct |
148 ms |
15840 KB |
ok, correct split |
11 |
Correct |
133 ms |
15096 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 |
142 ms |
12112 KB |
ok, correct split |
16 |
Correct |
113 ms |
11384 KB |
ok, correct split |
17 |
Correct |
167 ms |
15736 KB |
ok, correct split |
18 |
Correct |
134 ms |
14416 KB |
ok, correct split |
19 |
Correct |
153 ms |
12796 KB |
ok, correct split |
20 |
Correct |
122 ms |
11256 KB |
ok, correct split |
21 |
Correct |
74 ms |
11704 KB |
ok, correct split |
22 |
Correct |
74 ms |
11632 KB |
ok, correct split |
23 |
Correct |
77 ms |
11632 KB |
ok, correct split |
24 |
Correct |
6 ms |
4984 KB |
ok, correct split |
25 |
Correct |
100 ms |
11360 KB |
ok, correct split |
26 |
Correct |
43 ms |
7672 KB |
ok, correct split |
27 |
Correct |
6 ms |
5112 KB |
ok, correct split |
28 |
Correct |
136 ms |
12920 KB |
ok, correct split |
29 |
Correct |
141 ms |
12664 KB |
ok, correct split |
30 |
Correct |
149 ms |
12664 KB |
ok, correct split |
31 |
Correct |
122 ms |
13528 KB |
ok, correct split |
32 |
Correct |
110 ms |
12640 KB |
ok, correct split |
33 |
Correct |
34 ms |
7288 KB |
ok, no valid answer |
34 |
Correct |
49 ms |
8184 KB |
ok, no valid answer |
35 |
Correct |
84 ms |
11552 KB |
ok, no valid answer |
36 |
Correct |
95 ms |
11384 KB |
ok, no valid answer |
37 |
Correct |
73 ms |
11632 KB |
ok, no valid answer |
38 |
Correct |
6 ms |
4984 KB |
ok, correct split |
39 |
Correct |
7 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 |
4988 KB |
ok, correct split |
43 |
Correct |
6 ms |
4984 KB |
ok, correct split |
44 |
Correct |
6 ms |
4984 KB |
ok, correct split |
45 |
Correct |
6 ms |
4984 KB |
ok, correct split |
46 |
Correct |
9 ms |
5240 KB |
ok, correct split |
47 |
Correct |
9 ms |
5240 KB |
ok, correct split |
48 |
Correct |
6 ms |
5112 KB |
ok, correct split |
49 |
Incorrect |
9 ms |
5240 KB |
jury found a solution, contestant did not |
50 |
Halted |
0 ms |
0 KB |
- |