// #include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001;
vector<int> find_split(int n, int A, int B, int C, vector<int> U, vector<int> V) {
vector<int> impossible(n);
ll k=min({A,B,C});
vvi g(n);
rep(i,U.size()){
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
}
vi lk(n,inf),dep(n,-1),par(n),sub(n,1),euler;
function<ll(ll,ll,ll)> dfs=[&](ll i,ll p,ll d){
euler.pb(i);
par[i]=p;dep[i]=d;
for(ll x:g[i])if(x!=p){
if(dep[x]==-1){
sub[i]+=dfs(x,i,d+1);
chmin(lk[i],lk[x]);
}
else chmin(lk[i],dep[x]);
}
return sub[i];
};dfs(0,-1,0);
auto sol=[&](ll sz,vector<bool> flag){
ll i=0;
while(!flag[i])i++;
flag[i]=false;
vi res;
function<void(ll)> dfs=[&](ll cur){
if(res.size()==sz)return;
res.pb(cur);
for(auto x:g[cur])if(flag[x]){
flag[x]=false;
dfs(x);
if(res.size()==sz)return;
}
};dfs(i);
return res;
};
auto answer=[&](vi al){
vb f1(n,false),f2(n,false),f3(n,true);
for(ll i:al)f1[i]=true;
rep(i,n)if(!f1[i])f2[i]=true;
if(al.size()*2>n)swap(f1,f2);
vi a=sol(k,f1),b=sol(n-min({A,B,C})-max({A,B,C}),f2);
for(ll i:a)f3[i]=false;
for(ll i:b)f3[i]=false;
vi c;rep(i,n)if(f3[i])c.pb(i);
if(A!=a.size())swap(a,b);
if(A!=a.size())swap(a,c);
if(B!=b.size())swap(b,c);
vector<int> res(n);
for(ll i:a)res[i]=1;
for(ll i:b)res[i]=2;
for(ll i:c)res[i]=3;
return res;
};
auto get_sub=[&](ll t){
vi res;
function<void(ll)> dfs=[&](ll i){
res.pb(i);
for(ll x:g[i])if(par[x]==i)dfs(x);
};dfs(t);
return res;
};
ll rt;
for(ll i:euler)if(sub[i]*2>=n)rt=i;
for(ll x:g[rt])if(par[x]==rt&&sub[x]>=k)return answer(get_sub(x));
vi al;al.pb(rt);
for(ll x:g[rt])if(par[x]==rt&&lk[x]>=dep[rt]){
vi tmp=get_sub(x);
for(ll y:tmp)al.pb(y);
}
if(al.size()>n-k)return impossible;
for(ll x:g[rt])if(par[x]==rt&&lk[x]<dep[rt]&&al.size()<k){
vi tmp=get_sub(x);
for(ll y:tmp)al.pb(y);
}
return answer(al);
}
Compilation message
split.cpp: In lambda function:
split.cpp:57:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
57 | if(res.size()==sz)return;
| ~~~~~~~~~~^~~~
split.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
62 | if(res.size()==sz)return;
| ~~~~~~~~~~^~~~
split.cpp: In lambda function:
split.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
71 | if(al.size()*2>n)swap(f1,f2);
| ~~~~~~~~~~~^~
split.cpp:76:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(A!=a.size())swap(a,b);
| ~^~~~~~~~~~
split.cpp:77:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if(A!=a.size())swap(a,c);
| ~^~~~~~~~~~
split.cpp:78:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(B!=b.size())swap(b,c);
| ~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:101:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
101 | if(al.size()>n-k)return impossible;
| ~~~~~~~~~^~~~
split.cpp:102:59: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
102 | for(ll x:g[rt])if(par[x]==rt&&lk[x]<dep[rt]&&al.size()<k){
| ~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
ok, correct split |
2 |
Correct |
1 ms |
212 KB |
ok, correct split |
3 |
Correct |
0 ms |
212 KB |
ok, correct split |
4 |
Correct |
0 ms |
212 KB |
ok, correct split |
5 |
Correct |
1 ms |
212 KB |
ok, correct split |
6 |
Correct |
1 ms |
212 KB |
ok, correct split |
7 |
Correct |
108 ms |
24016 KB |
ok, correct split |
8 |
Correct |
99 ms |
21308 KB |
ok, correct split |
9 |
Correct |
94 ms |
19808 KB |
ok, correct split |
10 |
Correct |
105 ms |
25000 KB |
ok, correct split |
11 |
Correct |
106 ms |
24556 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
ok, correct split |
2 |
Correct |
1 ms |
212 KB |
ok, correct split |
3 |
Correct |
1 ms |
212 KB |
ok, correct split |
4 |
Correct |
133 ms |
21628 KB |
ok, correct split |
5 |
Correct |
81 ms |
13620 KB |
ok, correct split |
6 |
Correct |
106 ms |
25056 KB |
ok, correct split |
7 |
Correct |
105 ms |
20552 KB |
ok, correct split |
8 |
Correct |
129 ms |
17796 KB |
ok, correct split |
9 |
Correct |
107 ms |
13560 KB |
ok, correct split |
10 |
Correct |
58 ms |
13676 KB |
ok, correct split |
11 |
Correct |
62 ms |
13676 KB |
ok, correct split |
12 |
Correct |
52 ms |
13756 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
ok, correct split |
2 |
Correct |
86 ms |
15188 KB |
ok, correct split |
3 |
Correct |
26 ms |
6340 KB |
ok, correct split |
4 |
Correct |
1 ms |
212 KB |
ok, correct split |
5 |
Correct |
108 ms |
18488 KB |
ok, correct split |
6 |
Correct |
90 ms |
18092 KB |
ok, correct split |
7 |
Correct |
104 ms |
18624 KB |
ok, correct split |
8 |
Correct |
97 ms |
19736 KB |
ok, correct split |
9 |
Correct |
111 ms |
18416 KB |
ok, correct split |
10 |
Correct |
24 ms |
5444 KB |
ok, no valid answer |
11 |
Correct |
54 ms |
7600 KB |
ok, no valid answer |
12 |
Correct |
71 ms |
15020 KB |
ok, no valid answer |
13 |
Correct |
86 ms |
15056 KB |
ok, no valid answer |
14 |
Correct |
64 ms |
15136 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
ok, correct split |
2 |
Correct |
0 ms |
212 KB |
ok, no valid answer |
3 |
Correct |
0 ms |
212 KB |
ok, correct split |
4 |
Correct |
0 ms |
212 KB |
ok, correct split |
5 |
Correct |
0 ms |
212 KB |
ok, correct split |
6 |
Correct |
1 ms |
212 KB |
ok, correct split |
7 |
Correct |
0 ms |
212 KB |
ok, correct split |
8 |
Correct |
1 ms |
212 KB |
ok, correct split |
9 |
Correct |
3 ms |
724 KB |
ok, correct split |
10 |
Correct |
2 ms |
724 KB |
ok, correct split |
11 |
Correct |
1 ms |
212 KB |
ok, correct split |
12 |
Correct |
2 ms |
724 KB |
ok, correct split |
13 |
Correct |
1 ms |
212 KB |
ok, correct split |
14 |
Correct |
0 ms |
212 KB |
ok, correct split |
15 |
Correct |
0 ms |
212 KB |
ok, correct split |
16 |
Correct |
1 ms |
212 KB |
ok, correct split |
17 |
Correct |
1 ms |
212 KB |
ok, correct split |
18 |
Correct |
1 ms |
212 KB |
ok, correct split |
19 |
Correct |
1 ms |
340 KB |
ok, correct split |
20 |
Correct |
1 ms |
468 KB |
ok, correct split |
21 |
Correct |
2 ms |
724 KB |
ok, correct split |
22 |
Correct |
2 ms |
724 KB |
ok, correct split |
23 |
Correct |
3 ms |
724 KB |
ok, correct split |
24 |
Correct |
2 ms |
724 KB |
ok, correct split |
25 |
Correct |
2 ms |
692 KB |
ok, correct split |
26 |
Correct |
3 ms |
636 KB |
ok, correct split |
27 |
Correct |
2 ms |
724 KB |
ok, correct split |
28 |
Correct |
2 ms |
720 KB |
ok, correct split |
29 |
Correct |
1 ms |
340 KB |
ok, correct split |
30 |
Correct |
2 ms |
756 KB |
ok, correct split |
31 |
Correct |
1 ms |
340 KB |
ok, correct split |
32 |
Correct |
1 ms |
340 KB |
ok, correct split |
33 |
Correct |
1 ms |
308 KB |
ok, correct split |
34 |
Correct |
2 ms |
596 KB |
ok, correct split |
35 |
Correct |
2 ms |
596 KB |
ok, correct split |
36 |
Correct |
3 ms |
596 KB |
ok, correct split |
37 |
Correct |
3 ms |
724 KB |
ok, correct split |
38 |
Correct |
3 ms |
824 KB |
ok, correct split |
39 |
Correct |
3 ms |
724 KB |
ok, correct split |
40 |
Correct |
3 ms |
724 KB |
ok, correct split |
41 |
Correct |
3 ms |
468 KB |
ok, correct split |
42 |
Correct |
2 ms |
468 KB |
ok, correct split |
43 |
Correct |
4 ms |
724 KB |
ok, correct split |
44 |
Correct |
3 ms |
724 KB |
ok, correct split |
45 |
Correct |
3 ms |
724 KB |
ok, correct split |
46 |
Correct |
2 ms |
724 KB |
ok, correct split |
47 |
Correct |
2 ms |
724 KB |
ok, no valid answer |
48 |
Correct |
3 ms |
596 KB |
ok, correct split |
49 |
Correct |
2 ms |
820 KB |
ok, correct split |
50 |
Correct |
1 ms |
212 KB |
ok, no valid answer |
51 |
Correct |
1 ms |
300 KB |
ok, no valid answer |
52 |
Correct |
2 ms |
692 KB |
ok, no valid answer |
53 |
Correct |
3 ms |
724 KB |
ok, no valid answer |
54 |
Correct |
2 ms |
596 KB |
ok, no valid answer |
55 |
Correct |
2 ms |
696 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
596 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
ok, correct split |
2 |
Correct |
1 ms |
212 KB |
ok, correct split |
3 |
Correct |
0 ms |
212 KB |
ok, correct split |
4 |
Correct |
0 ms |
212 KB |
ok, correct split |
5 |
Correct |
1 ms |
212 KB |
ok, correct split |
6 |
Correct |
1 ms |
212 KB |
ok, correct split |
7 |
Correct |
108 ms |
24016 KB |
ok, correct split |
8 |
Correct |
99 ms |
21308 KB |
ok, correct split |
9 |
Correct |
94 ms |
19808 KB |
ok, correct split |
10 |
Correct |
105 ms |
25000 KB |
ok, correct split |
11 |
Correct |
106 ms |
24556 KB |
ok, correct split |
12 |
Correct |
0 ms |
212 KB |
ok, correct split |
13 |
Correct |
1 ms |
212 KB |
ok, correct split |
14 |
Correct |
1 ms |
212 KB |
ok, correct split |
15 |
Correct |
133 ms |
21628 KB |
ok, correct split |
16 |
Correct |
81 ms |
13620 KB |
ok, correct split |
17 |
Correct |
106 ms |
25056 KB |
ok, correct split |
18 |
Correct |
105 ms |
20552 KB |
ok, correct split |
19 |
Correct |
129 ms |
17796 KB |
ok, correct split |
20 |
Correct |
107 ms |
13560 KB |
ok, correct split |
21 |
Correct |
58 ms |
13676 KB |
ok, correct split |
22 |
Correct |
62 ms |
13676 KB |
ok, correct split |
23 |
Correct |
52 ms |
13756 KB |
ok, correct split |
24 |
Correct |
1 ms |
212 KB |
ok, correct split |
25 |
Correct |
86 ms |
15188 KB |
ok, correct split |
26 |
Correct |
26 ms |
6340 KB |
ok, correct split |
27 |
Correct |
1 ms |
212 KB |
ok, correct split |
28 |
Correct |
108 ms |
18488 KB |
ok, correct split |
29 |
Correct |
90 ms |
18092 KB |
ok, correct split |
30 |
Correct |
104 ms |
18624 KB |
ok, correct split |
31 |
Correct |
97 ms |
19736 KB |
ok, correct split |
32 |
Correct |
111 ms |
18416 KB |
ok, correct split |
33 |
Correct |
24 ms |
5444 KB |
ok, no valid answer |
34 |
Correct |
54 ms |
7600 KB |
ok, no valid answer |
35 |
Correct |
71 ms |
15020 KB |
ok, no valid answer |
36 |
Correct |
86 ms |
15056 KB |
ok, no valid answer |
37 |
Correct |
64 ms |
15136 KB |
ok, no valid answer |
38 |
Correct |
0 ms |
212 KB |
ok, correct split |
39 |
Correct |
0 ms |
212 KB |
ok, no valid answer |
40 |
Correct |
0 ms |
212 KB |
ok, correct split |
41 |
Correct |
0 ms |
212 KB |
ok, correct split |
42 |
Correct |
0 ms |
212 KB |
ok, correct split |
43 |
Correct |
1 ms |
212 KB |
ok, correct split |
44 |
Correct |
0 ms |
212 KB |
ok, correct split |
45 |
Correct |
1 ms |
212 KB |
ok, correct split |
46 |
Correct |
3 ms |
724 KB |
ok, correct split |
47 |
Correct |
2 ms |
724 KB |
ok, correct split |
48 |
Correct |
1 ms |
212 KB |
ok, correct split |
49 |
Correct |
2 ms |
724 KB |
ok, correct split |
50 |
Correct |
1 ms |
212 KB |
ok, correct split |
51 |
Correct |
0 ms |
212 KB |
ok, correct split |
52 |
Correct |
0 ms |
212 KB |
ok, correct split |
53 |
Correct |
1 ms |
212 KB |
ok, correct split |
54 |
Correct |
1 ms |
212 KB |
ok, correct split |
55 |
Correct |
1 ms |
212 KB |
ok, correct split |
56 |
Correct |
1 ms |
340 KB |
ok, correct split |
57 |
Correct |
1 ms |
468 KB |
ok, correct split |
58 |
Correct |
2 ms |
724 KB |
ok, correct split |
59 |
Correct |
2 ms |
724 KB |
ok, correct split |
60 |
Correct |
3 ms |
724 KB |
ok, correct split |
61 |
Correct |
2 ms |
724 KB |
ok, correct split |
62 |
Correct |
2 ms |
692 KB |
ok, correct split |
63 |
Correct |
3 ms |
636 KB |
ok, correct split |
64 |
Correct |
2 ms |
724 KB |
ok, correct split |
65 |
Correct |
2 ms |
720 KB |
ok, correct split |
66 |
Correct |
1 ms |
340 KB |
ok, correct split |
67 |
Correct |
2 ms |
756 KB |
ok, correct split |
68 |
Correct |
1 ms |
340 KB |
ok, correct split |
69 |
Correct |
1 ms |
340 KB |
ok, correct split |
70 |
Correct |
1 ms |
308 KB |
ok, correct split |
71 |
Correct |
2 ms |
596 KB |
ok, correct split |
72 |
Correct |
2 ms |
596 KB |
ok, correct split |
73 |
Correct |
3 ms |
596 KB |
ok, correct split |
74 |
Correct |
3 ms |
724 KB |
ok, correct split |
75 |
Correct |
3 ms |
824 KB |
ok, correct split |
76 |
Correct |
3 ms |
724 KB |
ok, correct split |
77 |
Correct |
3 ms |
724 KB |
ok, correct split |
78 |
Correct |
3 ms |
468 KB |
ok, correct split |
79 |
Correct |
2 ms |
468 KB |
ok, correct split |
80 |
Correct |
4 ms |
724 KB |
ok, correct split |
81 |
Correct |
3 ms |
724 KB |
ok, correct split |
82 |
Correct |
3 ms |
724 KB |
ok, correct split |
83 |
Correct |
2 ms |
724 KB |
ok, correct split |
84 |
Correct |
2 ms |
724 KB |
ok, no valid answer |
85 |
Correct |
3 ms |
596 KB |
ok, correct split |
86 |
Correct |
2 ms |
820 KB |
ok, correct split |
87 |
Correct |
1 ms |
212 KB |
ok, no valid answer |
88 |
Correct |
1 ms |
300 KB |
ok, no valid answer |
89 |
Correct |
2 ms |
692 KB |
ok, no valid answer |
90 |
Correct |
3 ms |
724 KB |
ok, no valid answer |
91 |
Correct |
2 ms |
596 KB |
ok, no valid answer |
92 |
Correct |
2 ms |
696 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
596 KB |
ok, no valid answer |
94 |
Correct |
126 ms |
19392 KB |
ok, correct split |
95 |
Correct |
187 ms |
27068 KB |
ok, correct split |
96 |
Correct |
126 ms |
24636 KB |
ok, correct split |
97 |
Correct |
25 ms |
6060 KB |
ok, correct split |
98 |
Correct |
38 ms |
6480 KB |
ok, correct split |
99 |
Correct |
59 ms |
9700 KB |
ok, correct split |
100 |
Correct |
120 ms |
20716 KB |
ok, correct split |
101 |
Correct |
119 ms |
19112 KB |
ok, correct split |
102 |
Correct |
131 ms |
17608 KB |
ok, correct split |
103 |
Correct |
93 ms |
17488 KB |
ok, correct split |
104 |
Correct |
139 ms |
18896 KB |
ok, correct split |
105 |
Correct |
60 ms |
9672 KB |
ok, correct split |
106 |
Correct |
126 ms |
19472 KB |
ok, correct split |
107 |
Correct |
97 ms |
15792 KB |
ok, correct split |
108 |
Correct |
88 ms |
15688 KB |
ok, correct split |
109 |
Correct |
159 ms |
20420 KB |
ok, correct split |
110 |
Correct |
153 ms |
20928 KB |
ok, correct split |
111 |
Correct |
145 ms |
21036 KB |
ok, correct split |
112 |
Correct |
132 ms |
20276 KB |
ok, correct split |
113 |
Correct |
116 ms |
20284 KB |
ok, correct split |
114 |
Correct |
17 ms |
2764 KB |
ok, correct split |
115 |
Correct |
10 ms |
2388 KB |
ok, correct split |
116 |
Correct |
150 ms |
20140 KB |
ok, correct split |
117 |
Correct |
117 ms |
20096 KB |
ok, correct split |
118 |
Correct |
99 ms |
14884 KB |
ok, correct split |
119 |
Correct |
103 ms |
14296 KB |
ok, correct split |
120 |
Correct |
105 ms |
20420 KB |
ok, correct split |
121 |
Correct |
80 ms |
14912 KB |
ok, no valid answer |
122 |
Correct |
87 ms |
15136 KB |
ok, no valid answer |
123 |
Correct |
155 ms |
20884 KB |
ok, no valid answer |
124 |
Correct |
155 ms |
20648 KB |
ok, no valid answer |
125 |
Correct |
132 ms |
16092 KB |
ok, no valid answer |
126 |
Correct |
74 ms |
13764 KB |
ok, no valid answer |
127 |
Correct |
133 ms |
16524 KB |
ok, no valid answer |