#include "split.h"
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
vector<int> al[100005];
int color,num;
vector<int> res;
int subtree[100005];
int parent[100005];
void dfs(int i){
res[i]=color;
num--;
if (!num) return;
for (vector<int>::iterator it=al[i].begin();it!=al[i].end();it++){
if (!res[*it]) dfs(*it);
if (!num) return;
}
}
void sub(int i,int p){
parent[i]=p;
for (vector<int>::iterator it=al[i].begin();it!=al[i].end();it++){
if (*it==p) continue;
sub(*it,i);
subtree[i]+=subtree[*it];
}
subtree[i]++;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res=vector<int> (n,0);
for (int x=0;x<p.size();x++){
al[p[x]].push_back(q[x]);
al[q[x]].push_back(p[x]);
}
if (a==1){
if (b>c) num=c,color=3;
else num=b,color=2;
dfs(0);
color=(color==2)?3:2;
bool lone=true;
for (int x=0;x<n;x++){
if (!res[x]){
if (lone){
lone=false;
res[x]=1;
}
else{
res[x]=color;
}
}
}
}
else if (n==p.size()+1){
vector<ii> col;
col.push_back(ii(a,1));
col.push_back(ii(b,2));
col.push_back(ii(c,3));
sort(col.begin(),col.end());
sub(0,-1);
for (int x=0;x<n;x++){
if (subtree[x]>=col[0].first && n-subtree[x]>=col[1].first){
res[x]=col[0].second;
res[parent[x]]=col[1].second;
color=col[1].second;
num=col[1].first;
dfs(parent[x]);
color=col[0].second;
num=col[0].first;
dfs(x);
for (int x=0;x<n;x++) if (res[x]==0) res[x]=col[2].second;
return res;
}
else if (subtree[x]>=col[1].first && n-subtree[x]>=col[0].first){
res[x]=col[1].second;
res[parent[x]]=col[0].second;
color=col[1].second;
num=col[1].first;
dfs(x);
color=col[0].second;
num=col[0].first;
dfs(parent[x]);
for (int x=0;x<n;x++) if (res[x]==0) res[x]=col[2].second;
return res;
}
}
return res;
}
else{
int pos=0;
for (int x=0;x<n;x++){
if (al[x].size()==1){
pos=x;
break;
}
}
while (a--){
res[pos]=1;
if (res[al[pos][0]]==0) pos=al[pos][0];
else pos=al[pos][1];
}
while (b--){
res[pos]=2;
if (res[al[pos][0]]==0) pos=al[pos][0];
else pos=al[pos][1];
}
for (int x=0;x<n;x++) if (res[x]==0) res[x]=3;
}
return res;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int x=0;x<p.size();x++){
~^~~~~~~~~
split.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if (n==p.size()+1){
~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
2 |
Correct |
4 ms |
2680 KB |
ok, correct split |
3 |
Correct |
4 ms |
2680 KB |
ok, correct split |
4 |
Correct |
4 ms |
2684 KB |
ok, correct split |
5 |
Correct |
4 ms |
2680 KB |
ok, correct split |
6 |
Correct |
4 ms |
2680 KB |
ok, correct split |
7 |
Correct |
105 ms |
13928 KB |
ok, correct split |
8 |
Correct |
74 ms |
8568 KB |
ok, correct split |
9 |
Correct |
94 ms |
12152 KB |
ok, correct split |
10 |
Correct |
73 ms |
8696 KB |
ok, correct split |
11 |
Correct |
78 ms |
8568 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
2 |
Correct |
4 ms |
2680 KB |
ok, correct split |
3 |
Correct |
4 ms |
2680 KB |
ok, correct split |
4 |
Correct |
95 ms |
10060 KB |
ok, correct split |
5 |
Correct |
78 ms |
9012 KB |
ok, correct split |
6 |
Correct |
76 ms |
8888 KB |
ok, correct split |
7 |
Correct |
97 ms |
10560 KB |
ok, correct split |
8 |
Correct |
122 ms |
11256 KB |
ok, correct split |
9 |
Correct |
83 ms |
8952 KB |
ok, correct split |
10 |
Correct |
62 ms |
9328 KB |
ok, correct split |
11 |
Correct |
63 ms |
9328 KB |
ok, correct split |
12 |
Correct |
64 ms |
9328 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
2 |
Correct |
88 ms |
9760 KB |
ok, correct split |
3 |
Correct |
32 ms |
5624 KB |
ok, correct split |
4 |
Correct |
4 ms |
2680 KB |
ok, correct split |
5 |
Correct |
96 ms |
11700 KB |
ok, correct split |
6 |
Correct |
96 ms |
11516 KB |
ok, correct split |
7 |
Correct |
93 ms |
11512 KB |
ok, correct split |
8 |
Correct |
101 ms |
12184 KB |
ok, correct split |
9 |
Correct |
90 ms |
11256 KB |
ok, correct split |
10 |
Correct |
26 ms |
5112 KB |
ok, no valid answer |
11 |
Correct |
38 ms |
6392 KB |
ok, no valid answer |
12 |
Correct |
70 ms |
10356 KB |
ok, no valid answer |
13 |
Correct |
78 ms |
10232 KB |
ok, no valid answer |
14 |
Correct |
65 ms |
10480 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
2680 KB |
invalid split: #1=3, #2=2, #3=4 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
2 |
Correct |
4 ms |
2680 KB |
ok, correct split |
3 |
Correct |
4 ms |
2680 KB |
ok, correct split |
4 |
Correct |
4 ms |
2684 KB |
ok, correct split |
5 |
Correct |
4 ms |
2680 KB |
ok, correct split |
6 |
Correct |
4 ms |
2680 KB |
ok, correct split |
7 |
Correct |
105 ms |
13928 KB |
ok, correct split |
8 |
Correct |
74 ms |
8568 KB |
ok, correct split |
9 |
Correct |
94 ms |
12152 KB |
ok, correct split |
10 |
Correct |
73 ms |
8696 KB |
ok, correct split |
11 |
Correct |
78 ms |
8568 KB |
ok, correct split |
12 |
Correct |
4 ms |
2680 KB |
ok, correct split |
13 |
Correct |
4 ms |
2680 KB |
ok, correct split |
14 |
Correct |
4 ms |
2680 KB |
ok, correct split |
15 |
Correct |
95 ms |
10060 KB |
ok, correct split |
16 |
Correct |
78 ms |
9012 KB |
ok, correct split |
17 |
Correct |
76 ms |
8888 KB |
ok, correct split |
18 |
Correct |
97 ms |
10560 KB |
ok, correct split |
19 |
Correct |
122 ms |
11256 KB |
ok, correct split |
20 |
Correct |
83 ms |
8952 KB |
ok, correct split |
21 |
Correct |
62 ms |
9328 KB |
ok, correct split |
22 |
Correct |
63 ms |
9328 KB |
ok, correct split |
23 |
Correct |
64 ms |
9328 KB |
ok, correct split |
24 |
Correct |
4 ms |
2680 KB |
ok, correct split |
25 |
Correct |
88 ms |
9760 KB |
ok, correct split |
26 |
Correct |
32 ms |
5624 KB |
ok, correct split |
27 |
Correct |
4 ms |
2680 KB |
ok, correct split |
28 |
Correct |
96 ms |
11700 KB |
ok, correct split |
29 |
Correct |
96 ms |
11516 KB |
ok, correct split |
30 |
Correct |
93 ms |
11512 KB |
ok, correct split |
31 |
Correct |
101 ms |
12184 KB |
ok, correct split |
32 |
Correct |
90 ms |
11256 KB |
ok, correct split |
33 |
Correct |
26 ms |
5112 KB |
ok, no valid answer |
34 |
Correct |
38 ms |
6392 KB |
ok, no valid answer |
35 |
Correct |
70 ms |
10356 KB |
ok, no valid answer |
36 |
Correct |
78 ms |
10232 KB |
ok, no valid answer |
37 |
Correct |
65 ms |
10480 KB |
ok, no valid answer |
38 |
Incorrect |
4 ms |
2680 KB |
invalid split: #1=3, #2=2, #3=4 |
39 |
Halted |
0 ms |
0 KB |
- |