#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
#include "split.h"
int par5[100001];
int par2[100001];
vector<int> adj[100001];
vector<int> adj2[100001];
vector<int> adj3[100001];
int find(int no){
if(par5[no]==no){
return no;
}
par5[no]=find(par5[no]);
return par5[no];
}
int nn;
int s[100001];
void dfs(int no,int par=-1){
s[no]=1;
for(auto j:adj[no]){
if(j!=par){
dfs(j,no);
s[no]+=s[j];
}
}
}
int dfs2(int no,int par=-1){
for(auto j:adj[no]){
if(j!=par){
if(s[j]>(nn/2)){
return dfs2(j,no);
}
}
}
return no;
}
void dfs3(int no,int par=-1,int xx=-1){
par2[no]=xx;
s[no]=1;
for(auto j:adj[no]){
if(j!=par){
if(par==-1){
dfs3(j,no,j);
}
else{
dfs3(j,no,xx);
}
s[no]+=s[j];
}
}
}
int vis[100001];
int su=0;
int ac=0;
vector<int> cur;
void dfs4(int no){
vis[no]=1;
if(su<ac){
su+=s[no];
cur.pb(no);
}
for(auto j:adj2[no]){
if(vis[j]==0){
dfs4(j);
}
}
}
void dfs5(int no){
vis[no]=1;
if(cur.size()<ac){
cur.pb(no);
}
for(auto j:adj3[no]){
if(vis[j]==0){
dfs5(j);
}
}
}
vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
nn=n;
vector<pair<int,int>> ss;
ss.pb({aa,1});
ss.pb({bb,2});
ss.pb({cc,3});
sort(ss.begin(),ss.end());
ac=ss[0].a;
aa=ss[0].a;
bb=ss[1].a;
cc=ss[2].a;
for(int i=0;i<n;i++){
par5[i]=i;
}
vector<pair<int,int>> tt;
for(int i=0;i<p.size();i++){
int x=find(p[i]);
int y=find(q[i]);
if(x!=y){
par5[x]=y;
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
else{
tt.pb({p[i],q[i]});
}
}
dfs(0);
int cen=dfs2(0);
dfs3(cen);
for(auto j:tt){
int x=par2[j.a];
int y=par2[j.b];
if(x==-1 or y==-1 or x==y){
continue;
}
adj2[x].pb(y);
adj2[y].pb(x);
}
// cout<<cen<<"::"<<endl;
for(auto j:adj[cen]){
if(vis[j]==0){
cur.clear();
su=0;
dfs4(j);
set<int> xx;
for(auto i:cur){
xx.insert(i);
}
if(su>=aa and su<=(n/2)){
/*for(auto i:xx){
cout<<i<<":";
}
cout<<endl;*/
for(int i=0;i<n;i++){
vis[i]=0;
}
for(int i=0;i<p.size();i++){
if(xx.find(par2[p[i]])!=xx.end()){
if(xx.find(par2[q[i]])!=xx.end()){
adj3[p[i]].pb(q[i]);
adj3[q[i]].pb(p[i]);
}
}
}
ac=aa;
cur.clear();
dfs5(j);
vector<int> ha=cur;
for(int i=0;i<n;i++){
adj3[i].clear();
}
for(int i=0;i<p.size();i++){
if(xx.find(par2[p[i]])==xx.end()){
if(xx.find(par2[q[i]])==xx.end()){
adj3[p[i]].pb(q[i]);
adj3[q[i]].pb(p[i]);
}
}
}
ac=bb;
cur.clear();
for(int i=0;i<n;i++){
vis[i]=0;
}
dfs5(cen);
vector<int> hb=cur;
vector<int> ans;
for(int i=0;i<n;i++){
ans.pb(3);
}
for(auto j:ha){
ans[j]=1;
}
for(auto j:hb){
ans[j]=2;
}
map<int,int> mm;
mm[1]=ss[0].b;
mm[2]=ss[1].b;
mm[3]=ss[2].b;
for(int i=0;i<n;i++){
ans[i]=mm[ans[i]];
}
return ans;
}
else if(su>=aa){
for(int i=0;i<n;i++){
vis[i]=0;
}
for(int i=0;i<p.size();i++){
if(xx.find(par2[p[i]])!=xx.end()){
if(xx.find(par2[q[i]])!=xx.end()){
adj3[p[i]].pb(q[i]);
adj3[q[i]].pb(p[i]);
}
}
}
ac=bb;
cur.clear();
dfs5(j);
vector<int> ha=cur;
for(int i=0;i<n;i++){
adj3[i].clear();
}
for(int i=0;i<p.size();i++){
if(xx.find(par2[p[i]])==xx.end()){
if(xx.find(par2[q[i]])==xx.end()){
adj3[p[i]].pb(q[i]);
adj3[q[i]].pb(p[i]);
}
}
}
ac=aa;
cur.clear();
for(int i=0;i<n;i++){
vis[i]=0;
}
dfs5(cen);
vector<int> hb=cur;
vector<int> ans;
for(int i=0;i<n;i++){
ans.pb(3);
}
for(auto j:ha){
ans[j]=2;
}
for(auto j:hb){
ans[j]=1;
}
map<int,int> mm;
mm[1]=ss[0].b;
mm[2]=ss[1].b;
mm[3]=ss[2].b;
for(int i=0;i<n;i++){
ans[i]=mm[ans[i]];
}
return ans;
}
else{
continue;
}
}
}
vector<int> res;
for(int i=0;i<n;i++){
res.pb(0);
}
return res;
}
Compilation message
split.cpp: In function 'void dfs5(int)':
split.cpp:78:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
78 | if(cur.size()<ac){
| ~~~~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0;i<p.size();i++){
| ~^~~~~~~~~
split.cpp:148:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int i=0;i<p.size();i++){
| ~^~~~~~~~~
split.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int i=0;i<p.size();i++){
| ~^~~~~~~~~
split.cpp:205:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | for(int i=0;i<p.size();i++){
| ~^~~~~~~~~
split.cpp:222:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | for(int i=0;i<p.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
6 ms |
7364 KB |
ok, correct split |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
4 ms |
7380 KB |
ok, correct split |
5 |
Correct |
4 ms |
7380 KB |
ok, correct split |
6 |
Correct |
5 ms |
7372 KB |
ok, correct split |
7 |
Correct |
112 ms |
26284 KB |
ok, correct split |
8 |
Correct |
109 ms |
23736 KB |
ok, correct split |
9 |
Correct |
135 ms |
23352 KB |
ok, correct split |
10 |
Correct |
101 ms |
25984 KB |
ok, correct split |
11 |
Correct |
131 ms |
25144 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7252 KB |
ok, correct split |
2 |
Correct |
4 ms |
7252 KB |
ok, correct split |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
165 ms |
23196 KB |
ok, correct split |
5 |
Correct |
112 ms |
19068 KB |
ok, correct split |
6 |
Correct |
133 ms |
26040 KB |
ok, correct split |
7 |
Correct |
176 ms |
23868 KB |
ok, correct split |
8 |
Correct |
168 ms |
23236 KB |
ok, correct split |
9 |
Correct |
124 ms |
18912 KB |
ok, correct split |
10 |
Correct |
97 ms |
19404 KB |
ok, correct split |
11 |
Correct |
67 ms |
19396 KB |
ok, correct split |
12 |
Correct |
65 ms |
19780 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7380 KB |
ok, correct split |
2 |
Correct |
138 ms |
19132 KB |
ok, correct split |
3 |
Correct |
55 ms |
11960 KB |
ok, correct split |
4 |
Correct |
6 ms |
7364 KB |
ok, correct split |
5 |
Correct |
148 ms |
21472 KB |
ok, correct split |
6 |
Correct |
139 ms |
21200 KB |
ok, correct split |
7 |
Correct |
155 ms |
21220 KB |
ok, correct split |
8 |
Correct |
145 ms |
22416 KB |
ok, correct split |
9 |
Correct |
118 ms |
21232 KB |
ok, correct split |
10 |
Correct |
24 ms |
10140 KB |
ok, no valid answer |
11 |
Correct |
45 ms |
11464 KB |
ok, no valid answer |
12 |
Correct |
99 ms |
15796 KB |
ok, no valid answer |
13 |
Correct |
80 ms |
15540 KB |
ok, no valid answer |
14 |
Correct |
63 ms |
15824 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
5 ms |
7264 KB |
ok, correct split |
5 |
Correct |
5 ms |
7380 KB |
ok, correct split |
6 |
Correct |
4 ms |
7360 KB |
ok, correct split |
7 |
Correct |
5 ms |
7364 KB |
ok, correct split |
8 |
Correct |
5 ms |
7300 KB |
ok, correct split |
9 |
Correct |
7 ms |
7636 KB |
ok, correct split |
10 |
Correct |
7 ms |
7636 KB |
ok, correct split |
11 |
Correct |
5 ms |
7364 KB |
ok, correct split |
12 |
Correct |
11 ms |
7764 KB |
ok, correct split |
13 |
Correct |
6 ms |
7252 KB |
ok, correct split |
14 |
Correct |
6 ms |
7252 KB |
ok, correct split |
15 |
Correct |
4 ms |
7348 KB |
ok, correct split |
16 |
Correct |
5 ms |
7380 KB |
ok, correct split |
17 |
Correct |
4 ms |
7252 KB |
ok, correct split |
18 |
Correct |
4 ms |
7252 KB |
ok, correct split |
19 |
Correct |
4 ms |
7428 KB |
ok, correct split |
20 |
Correct |
4 ms |
7380 KB |
ok, correct split |
21 |
Correct |
6 ms |
7632 KB |
ok, correct split |
22 |
Correct |
8 ms |
7660 KB |
ok, correct split |
23 |
Correct |
8 ms |
7636 KB |
ok, correct split |
24 |
Correct |
8 ms |
7636 KB |
ok, correct split |
25 |
Correct |
7 ms |
7636 KB |
ok, correct split |
26 |
Correct |
6 ms |
7764 KB |
ok, correct split |
27 |
Correct |
6 ms |
7764 KB |
ok, correct split |
28 |
Correct |
7 ms |
7764 KB |
ok, correct split |
29 |
Correct |
5 ms |
7380 KB |
ok, correct split |
30 |
Correct |
9 ms |
7764 KB |
ok, correct split |
31 |
Correct |
6 ms |
7380 KB |
ok, correct split |
32 |
Correct |
4 ms |
7368 KB |
ok, correct split |
33 |
Correct |
5 ms |
7380 KB |
ok, correct split |
34 |
Correct |
6 ms |
7632 KB |
ok, correct split |
35 |
Correct |
8 ms |
7660 KB |
ok, correct split |
36 |
Correct |
6 ms |
7636 KB |
ok, correct split |
37 |
Correct |
8 ms |
7764 KB |
ok, correct split |
38 |
Correct |
10 ms |
7756 KB |
ok, correct split |
39 |
Correct |
10 ms |
7764 KB |
ok, correct split |
40 |
Correct |
8 ms |
7764 KB |
ok, correct split |
41 |
Correct |
6 ms |
7508 KB |
ok, correct split |
42 |
Correct |
6 ms |
7508 KB |
ok, correct split |
43 |
Correct |
7 ms |
7760 KB |
ok, correct split |
44 |
Correct |
7 ms |
7764 KB |
ok, correct split |
45 |
Correct |
7 ms |
7696 KB |
ok, correct split |
46 |
Correct |
8 ms |
7632 KB |
ok, correct split |
47 |
Correct |
7 ms |
7632 KB |
ok, no valid answer |
48 |
Correct |
6 ms |
7636 KB |
ok, correct split |
49 |
Correct |
8 ms |
7636 KB |
ok, correct split |
50 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
51 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
52 |
Correct |
8 ms |
7508 KB |
ok, no valid answer |
53 |
Correct |
6 ms |
7568 KB |
ok, no valid answer |
54 |
Correct |
6 ms |
7500 KB |
ok, no valid answer |
55 |
Correct |
6 ms |
7636 KB |
ok, no valid answer |
56 |
Correct |
8 ms |
7508 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
ok, correct split |
2 |
Correct |
6 ms |
7364 KB |
ok, correct split |
3 |
Correct |
4 ms |
7252 KB |
ok, correct split |
4 |
Correct |
4 ms |
7380 KB |
ok, correct split |
5 |
Correct |
4 ms |
7380 KB |
ok, correct split |
6 |
Correct |
5 ms |
7372 KB |
ok, correct split |
7 |
Correct |
112 ms |
26284 KB |
ok, correct split |
8 |
Correct |
109 ms |
23736 KB |
ok, correct split |
9 |
Correct |
135 ms |
23352 KB |
ok, correct split |
10 |
Correct |
101 ms |
25984 KB |
ok, correct split |
11 |
Correct |
131 ms |
25144 KB |
ok, correct split |
12 |
Correct |
8 ms |
7252 KB |
ok, correct split |
13 |
Correct |
4 ms |
7252 KB |
ok, correct split |
14 |
Correct |
4 ms |
7252 KB |
ok, correct split |
15 |
Correct |
165 ms |
23196 KB |
ok, correct split |
16 |
Correct |
112 ms |
19068 KB |
ok, correct split |
17 |
Correct |
133 ms |
26040 KB |
ok, correct split |
18 |
Correct |
176 ms |
23868 KB |
ok, correct split |
19 |
Correct |
168 ms |
23236 KB |
ok, correct split |
20 |
Correct |
124 ms |
18912 KB |
ok, correct split |
21 |
Correct |
97 ms |
19404 KB |
ok, correct split |
22 |
Correct |
67 ms |
19396 KB |
ok, correct split |
23 |
Correct |
65 ms |
19780 KB |
ok, correct split |
24 |
Correct |
5 ms |
7380 KB |
ok, correct split |
25 |
Correct |
138 ms |
19132 KB |
ok, correct split |
26 |
Correct |
55 ms |
11960 KB |
ok, correct split |
27 |
Correct |
6 ms |
7364 KB |
ok, correct split |
28 |
Correct |
148 ms |
21472 KB |
ok, correct split |
29 |
Correct |
139 ms |
21200 KB |
ok, correct split |
30 |
Correct |
155 ms |
21220 KB |
ok, correct split |
31 |
Correct |
145 ms |
22416 KB |
ok, correct split |
32 |
Correct |
118 ms |
21232 KB |
ok, correct split |
33 |
Correct |
24 ms |
10140 KB |
ok, no valid answer |
34 |
Correct |
45 ms |
11464 KB |
ok, no valid answer |
35 |
Correct |
99 ms |
15796 KB |
ok, no valid answer |
36 |
Correct |
80 ms |
15540 KB |
ok, no valid answer |
37 |
Correct |
63 ms |
15824 KB |
ok, no valid answer |
38 |
Correct |
4 ms |
7252 KB |
ok, correct split |
39 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
7252 KB |
ok, correct split |
41 |
Correct |
5 ms |
7264 KB |
ok, correct split |
42 |
Correct |
5 ms |
7380 KB |
ok, correct split |
43 |
Correct |
4 ms |
7360 KB |
ok, correct split |
44 |
Correct |
5 ms |
7364 KB |
ok, correct split |
45 |
Correct |
5 ms |
7300 KB |
ok, correct split |
46 |
Correct |
7 ms |
7636 KB |
ok, correct split |
47 |
Correct |
7 ms |
7636 KB |
ok, correct split |
48 |
Correct |
5 ms |
7364 KB |
ok, correct split |
49 |
Correct |
11 ms |
7764 KB |
ok, correct split |
50 |
Correct |
6 ms |
7252 KB |
ok, correct split |
51 |
Correct |
6 ms |
7252 KB |
ok, correct split |
52 |
Correct |
4 ms |
7348 KB |
ok, correct split |
53 |
Correct |
5 ms |
7380 KB |
ok, correct split |
54 |
Correct |
4 ms |
7252 KB |
ok, correct split |
55 |
Correct |
4 ms |
7252 KB |
ok, correct split |
56 |
Correct |
4 ms |
7428 KB |
ok, correct split |
57 |
Correct |
4 ms |
7380 KB |
ok, correct split |
58 |
Correct |
6 ms |
7632 KB |
ok, correct split |
59 |
Correct |
8 ms |
7660 KB |
ok, correct split |
60 |
Correct |
8 ms |
7636 KB |
ok, correct split |
61 |
Correct |
8 ms |
7636 KB |
ok, correct split |
62 |
Correct |
7 ms |
7636 KB |
ok, correct split |
63 |
Correct |
6 ms |
7764 KB |
ok, correct split |
64 |
Correct |
6 ms |
7764 KB |
ok, correct split |
65 |
Correct |
7 ms |
7764 KB |
ok, correct split |
66 |
Correct |
5 ms |
7380 KB |
ok, correct split |
67 |
Correct |
9 ms |
7764 KB |
ok, correct split |
68 |
Correct |
6 ms |
7380 KB |
ok, correct split |
69 |
Correct |
4 ms |
7368 KB |
ok, correct split |
70 |
Correct |
5 ms |
7380 KB |
ok, correct split |
71 |
Correct |
6 ms |
7632 KB |
ok, correct split |
72 |
Correct |
8 ms |
7660 KB |
ok, correct split |
73 |
Correct |
6 ms |
7636 KB |
ok, correct split |
74 |
Correct |
8 ms |
7764 KB |
ok, correct split |
75 |
Correct |
10 ms |
7756 KB |
ok, correct split |
76 |
Correct |
10 ms |
7764 KB |
ok, correct split |
77 |
Correct |
8 ms |
7764 KB |
ok, correct split |
78 |
Correct |
6 ms |
7508 KB |
ok, correct split |
79 |
Correct |
6 ms |
7508 KB |
ok, correct split |
80 |
Correct |
7 ms |
7760 KB |
ok, correct split |
81 |
Correct |
7 ms |
7764 KB |
ok, correct split |
82 |
Correct |
7 ms |
7696 KB |
ok, correct split |
83 |
Correct |
8 ms |
7632 KB |
ok, correct split |
84 |
Correct |
7 ms |
7632 KB |
ok, no valid answer |
85 |
Correct |
6 ms |
7636 KB |
ok, correct split |
86 |
Correct |
8 ms |
7636 KB |
ok, correct split |
87 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
88 |
Correct |
4 ms |
7252 KB |
ok, no valid answer |
89 |
Correct |
8 ms |
7508 KB |
ok, no valid answer |
90 |
Correct |
6 ms |
7568 KB |
ok, no valid answer |
91 |
Correct |
6 ms |
7500 KB |
ok, no valid answer |
92 |
Correct |
6 ms |
7636 KB |
ok, no valid answer |
93 |
Correct |
8 ms |
7508 KB |
ok, no valid answer |
94 |
Correct |
114 ms |
20456 KB |
ok, correct split |
95 |
Correct |
153 ms |
25280 KB |
ok, correct split |
96 |
Correct |
143 ms |
23792 KB |
ok, correct split |
97 |
Correct |
49 ms |
12116 KB |
ok, correct split |
98 |
Correct |
38 ms |
12172 KB |
ok, correct split |
99 |
Correct |
50 ms |
14400 KB |
ok, correct split |
100 |
Correct |
153 ms |
23616 KB |
ok, correct split |
101 |
Correct |
129 ms |
22096 KB |
ok, correct split |
102 |
Correct |
133 ms |
23600 KB |
ok, correct split |
103 |
Correct |
116 ms |
22820 KB |
ok, correct split |
104 |
Correct |
132 ms |
25300 KB |
ok, correct split |
105 |
Correct |
54 ms |
14636 KB |
ok, correct split |
106 |
Correct |
104 ms |
25144 KB |
ok, correct split |
107 |
Correct |
93 ms |
19100 KB |
ok, correct split |
108 |
Correct |
89 ms |
19140 KB |
ok, correct split |
109 |
Correct |
193 ms |
23132 KB |
ok, correct split |
110 |
Correct |
203 ms |
25416 KB |
ok, correct split |
111 |
Correct |
231 ms |
25516 KB |
ok, correct split |
112 |
Correct |
207 ms |
25768 KB |
ok, correct split |
113 |
Correct |
191 ms |
25848 KB |
ok, correct split |
114 |
Correct |
18 ms |
9220 KB |
ok, correct split |
115 |
Correct |
18 ms |
9220 KB |
ok, correct split |
116 |
Correct |
142 ms |
24260 KB |
ok, correct split |
117 |
Correct |
145 ms |
24136 KB |
ok, correct split |
118 |
Correct |
131 ms |
19108 KB |
ok, correct split |
119 |
Correct |
84 ms |
19008 KB |
ok, correct split |
120 |
Correct |
109 ms |
21968 KB |
ok, correct split |
121 |
Correct |
61 ms |
15428 KB |
ok, no valid answer |
122 |
Correct |
95 ms |
15572 KB |
ok, no valid answer |
123 |
Correct |
106 ms |
18876 KB |
ok, no valid answer |
124 |
Correct |
89 ms |
19240 KB |
ok, no valid answer |
125 |
Correct |
72 ms |
17436 KB |
ok, no valid answer |
126 |
Correct |
47 ms |
15236 KB |
ok, no valid answer |
127 |
Correct |
86 ms |
18604 KB |
ok, no valid answer |