///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 100001
vector<int> color;
vector<int> e[N];
int s[N];
int A[N];
int B[N];
int C[N];
int y,z;
void dfs(int v,int u,int a,int b,int c){
s[v]=1;
for(auto& i:e[v]){
if(i==u) continue;
dfs(i,v,a,b,c);
s[v]+=s[i];
if(A[i]) A[v]=1;
if(B[i]) B[v]=1;
if(C[i]) C[v]=1;
}
if(s[v]==a) A[v]=1;
if(s[v]==b) B[v]=1;
if(s[v]==c) C[v]=1;
}
void Color(int v,int u,int a,int b,int c){
if(!z){
if(A[v] && s[v]==a+b) z=3;
if(B[v] && s[v]==a+b) z=3;
if(A[v] && s[v]==a+c) z=2;
if(C[v] && s[v]==a+c) z=2;
if(B[v] && s[v]==c+b) z=1;
if(C[v] && s[v]==c+b) z=1;
if(z) color[v]=4;
}
if(color[v]==4 && s[v]==a && z!=1 && !y){
color[v]=1;
y=5-z;
}
if(color[v]==4 && s[v]==b && z!=2 && !y){
color[v]=2;
y=4-z;
}
if(color[v]==4 && s[v]==c && z!=3 && !y){
color[v]=3;
y=3-z;
}
for(auto& i:e[v]){
if(i==u) continue;
color[i]=color[v];
Color(i,v,a,b,c);
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
for(int i=y=z=0;i<n-1;i++){
e[p[i]].append(q[i]);
e[q[i]].append(p[i]);
}
for(int i=0;i<n;i++)
color.append(0);
dfs(0,-1,a,b,c);
Color(0,-1,a,b,c);
if(!z){
dfs(1,-1,a,b,c);
Color(1,-1,a,b,c);
}
for(int i=0;i<n;i++){
if(color[i]==0) color[i]=z;
if(color[i]==4) color[i]=y;
}
return color;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3928 KB |
ok, correct split |
2 |
Correct |
1 ms |
3932 KB |
ok, correct split |
3 |
Correct |
1 ms |
3932 KB |
ok, correct split |
4 |
Correct |
1 ms |
3928 KB |
ok, correct split |
5 |
Correct |
1 ms |
3932 KB |
ok, correct split |
6 |
Correct |
1 ms |
4184 KB |
ok, correct split |
7 |
Correct |
64 ms |
17268 KB |
ok, correct split |
8 |
Correct |
51 ms |
15060 KB |
ok, correct split |
9 |
Correct |
50 ms |
14288 KB |
ok, correct split |
10 |
Correct |
53 ms |
17104 KB |
ok, correct split |
11 |
Correct |
52 ms |
16100 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3928 KB |
ok, correct split |
2 |
Correct |
1 ms |
3932 KB |
ok, correct split |
3 |
Runtime error |
642 ms |
1048576 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3928 KB |
ok, correct split |
2 |
Incorrect |
47 ms |
9776 KB |
jury found a solution, contestant did not |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
558 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3928 KB |
ok, correct split |
2 |
Correct |
1 ms |
3932 KB |
ok, correct split |
3 |
Correct |
1 ms |
3932 KB |
ok, correct split |
4 |
Correct |
1 ms |
3928 KB |
ok, correct split |
5 |
Correct |
1 ms |
3932 KB |
ok, correct split |
6 |
Correct |
1 ms |
4184 KB |
ok, correct split |
7 |
Correct |
64 ms |
17268 KB |
ok, correct split |
8 |
Correct |
51 ms |
15060 KB |
ok, correct split |
9 |
Correct |
50 ms |
14288 KB |
ok, correct split |
10 |
Correct |
53 ms |
17104 KB |
ok, correct split |
11 |
Correct |
52 ms |
16100 KB |
ok, correct split |
12 |
Correct |
1 ms |
3928 KB |
ok, correct split |
13 |
Correct |
1 ms |
3932 KB |
ok, correct split |
14 |
Runtime error |
642 ms |
1048576 KB |
Execution killed with signal 9 |
15 |
Halted |
0 ms |
0 KB |
- |