#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
pair<int,int> edges[nmax];
int n,m;
pair<int/*size*/,int/*colour*/> given[3];
vector<int> outp;
vector< pair<int,int> > extra,create_first;
int SZ[nmax],parent[nmax];
int root(int node)
{
if(parent[node]==node)return node;
parent[node]=root(parent[node]);
return parent[node];
}
vector<int> adj[nmax],all_adj[nmax];
int centroid;
void dfs(int node,int par)
{
SZ[node]=1;
for(auto k:adj[node])
if(k!=par)
{
dfs(k,node);
SZ[node]+=SZ[k];
}
}
int find_centroid()
{
dfs(0,0);
int ret=0;
while(SZ[ret]>SZ[0]/2)
{
bool stop=1;
for(auto k:adj[ret])
if(SZ[ret]>SZ[k]&&SZ[k]>SZ[0]/2)
{
stop=0;
ret=k;
break;
}
if(stop)break;
}
return ret;
}
void dfs_create_adj(int node)
{
//cout<<"dfs_create_adj "<<node<<endl;
if(given[0].first==0)return;
if(outp[node])return;
given[0].first--;
outp[node]=given[0].second;
//cout<<node<<" -> "<<outp[node]<<endl;
for(auto k:adj[node])
dfs_create_adj(k);
}
void dfs_create_all(int node)
{
//cout<<"dfs_create_all "<<node<<endl;
if(given[1].first==0)return;
if(outp[node])return;
given[1].first--;
outp[node]=given[1].second;
//cout<<node<<" -> "<<outp[node]<<endl;
for(auto k:all_adj[node])
dfs_create_all(k);
}
void fill_dumb()
{
for(auto &k:outp)
if(k==0)
{
k=given[2].second;
given[2].first--;
}
assert(given[0].first==0&&given[1].first==0&&given[2].first==0);
}
void push(vector< pair<int,int> > cur)
{
if(given[0].first==1)
{
dfs_create_adj((centroid==0?1:0));
dfs_create_all(centroid);
fill_dumb();
return;
}
for(auto k:cur)
if(k.first!=centroid&&k.second!=centroid&&root(k.first)!=root(k.second))
{
adj[k.first].push_back(k.second);
adj[k.second].push_back(k.first);
//cout<<"pushed "<<k.first<<" "<<k.second<<endl;
SZ[root(k.first)]+=SZ[root(k.second)];
parent[root(k.second)]=root(k.first);
if(SZ[root(k.first)]>=given[0].first)
{
dfs_create_adj(k.first);
dfs_create_all(centroid);
fill_dumb();
return;
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
n=N;
outp={};
for(int i=0;i<n;i++)
{
outp.push_back(0);
all_adj[i]={};
}
m=p.size();
given[0]={a,1};
given[1]={b,2};
given[2]={c,3};
sort(given,given+3);
for(int i=0;i<m;i++)
{
edges[i]={p[i],q[i]};
all_adj[p[i]].push_back(q[i]);
all_adj[q[i]].push_back(p[i]);
}
for(int i=0;i<n;i++)
{
SZ[i]=1;
parent[i]=i;
}
for(int i=0;i<m;i++)
if(root(p[i])!=root(q[i]))
{
SZ[root(p[i])]+=SZ[root(q[i])];
parent[root(q[i])]=root(p[i]);
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
create_first.push_back({p[i],q[i]});
}
else extra.push_back({p[i],q[i]});
centroid=find_centroid();
//cout<<"centroid= "<<centroid<<endl;
for(int i=0;i<n;i++)
{
adj[i]={};
SZ[i]=1;
parent[i]=i;
}
push(create_first);
if(outp[0])return outp;
push(extra);
return outp;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
ok, correct split |
2 |
Correct |
7 ms |
9728 KB |
ok, correct split |
3 |
Correct |
7 ms |
9728 KB |
ok, correct split |
4 |
Correct |
7 ms |
9728 KB |
ok, correct split |
5 |
Correct |
7 ms |
9728 KB |
ok, correct split |
6 |
Correct |
7 ms |
9728 KB |
ok, correct split |
7 |
Correct |
175 ms |
27116 KB |
ok, correct split |
8 |
Correct |
154 ms |
25196 KB |
ok, correct split |
9 |
Correct |
157 ms |
24684 KB |
ok, correct split |
10 |
Correct |
147 ms |
27116 KB |
ok, correct split |
11 |
Correct |
166 ms |
26220 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
ok, correct split |
2 |
Correct |
7 ms |
9728 KB |
ok, correct split |
3 |
Correct |
7 ms |
9728 KB |
ok, correct split |
4 |
Correct |
174 ms |
23212 KB |
ok, correct split |
5 |
Correct |
133 ms |
21356 KB |
ok, correct split |
6 |
Correct |
174 ms |
27116 KB |
ok, correct split |
7 |
Correct |
165 ms |
25068 KB |
ok, correct split |
8 |
Correct |
221 ms |
25324 KB |
ok, correct split |
9 |
Correct |
168 ms |
21100 KB |
ok, correct split |
10 |
Correct |
91 ms |
21868 KB |
ok, correct split |
11 |
Correct |
93 ms |
21996 KB |
ok, correct split |
12 |
Correct |
94 ms |
21868 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
ok, correct split |
2 |
Correct |
159 ms |
21356 KB |
ok, correct split |
3 |
Correct |
45 ms |
14320 KB |
ok, correct split |
4 |
Correct |
7 ms |
9728 KB |
ok, correct split |
5 |
Correct |
164 ms |
23148 KB |
ok, correct split |
6 |
Correct |
162 ms |
23020 KB |
ok, correct split |
7 |
Correct |
169 ms |
22768 KB |
ok, correct split |
8 |
Correct |
178 ms |
23916 KB |
ok, correct split |
9 |
Correct |
173 ms |
22636 KB |
ok, correct split |
10 |
Correct |
41 ms |
13564 KB |
ok, no valid answer |
11 |
Correct |
58 ms |
15472 KB |
ok, no valid answer |
12 |
Correct |
118 ms |
21868 KB |
ok, no valid answer |
13 |
Correct |
141 ms |
21356 KB |
ok, no valid answer |
14 |
Correct |
91 ms |
21868 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
ok, correct split |
2 |
Correct |
8 ms |
9728 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
9728 KB |
ok, correct split |
4 |
Correct |
7 ms |
9728 KB |
ok, correct split |
5 |
Correct |
7 ms |
9728 KB |
ok, correct split |
6 |
Correct |
7 ms |
9728 KB |
ok, correct split |
7 |
Correct |
7 ms |
9728 KB |
ok, correct split |
8 |
Correct |
7 ms |
9728 KB |
ok, correct split |
9 |
Correct |
10 ms |
10112 KB |
ok, correct split |
10 |
Correct |
10 ms |
10112 KB |
ok, correct split |
11 |
Correct |
7 ms |
9728 KB |
ok, correct split |
12 |
Correct |
10 ms |
10240 KB |
ok, correct split |
13 |
Correct |
7 ms |
9728 KB |
ok, correct split |
14 |
Correct |
8 ms |
9728 KB |
ok, correct split |
15 |
Correct |
7 ms |
9728 KB |
ok, correct split |
16 |
Correct |
8 ms |
9728 KB |
ok, correct split |
17 |
Correct |
8 ms |
9728 KB |
ok, correct split |
18 |
Correct |
7 ms |
9728 KB |
ok, correct split |
19 |
Correct |
7 ms |
9728 KB |
ok, correct split |
20 |
Correct |
9 ms |
9856 KB |
ok, correct split |
21 |
Correct |
9 ms |
10112 KB |
ok, correct split |
22 |
Correct |
9 ms |
10112 KB |
ok, correct split |
23 |
Correct |
9 ms |
10112 KB |
ok, correct split |
24 |
Correct |
9 ms |
10112 KB |
ok, correct split |
25 |
Correct |
9 ms |
10112 KB |
ok, correct split |
26 |
Correct |
10 ms |
10240 KB |
ok, correct split |
27 |
Correct |
11 ms |
10240 KB |
ok, correct split |
28 |
Correct |
10 ms |
10240 KB |
ok, correct split |
29 |
Correct |
7 ms |
9728 KB |
ok, correct split |
30 |
Correct |
10 ms |
10240 KB |
ok, correct split |
31 |
Correct |
8 ms |
9856 KB |
ok, correct split |
32 |
Correct |
7 ms |
9856 KB |
ok, correct split |
33 |
Correct |
7 ms |
9728 KB |
ok, correct split |
34 |
Correct |
9 ms |
10112 KB |
ok, correct split |
35 |
Correct |
10 ms |
10112 KB |
ok, correct split |
36 |
Correct |
9 ms |
10032 KB |
ok, correct split |
37 |
Correct |
11 ms |
10240 KB |
ok, correct split |
38 |
Correct |
10 ms |
10244 KB |
ok, correct split |
39 |
Correct |
10 ms |
10240 KB |
ok, correct split |
40 |
Correct |
10 ms |
10240 KB |
ok, correct split |
41 |
Correct |
9 ms |
9976 KB |
ok, correct split |
42 |
Correct |
8 ms |
9984 KB |
ok, correct split |
43 |
Correct |
10 ms |
10240 KB |
ok, correct split |
44 |
Correct |
11 ms |
10176 KB |
ok, correct split |
45 |
Correct |
10 ms |
10240 KB |
ok, correct split |
46 |
Correct |
9 ms |
10112 KB |
ok, correct split |
47 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
48 |
Correct |
9 ms |
10112 KB |
ok, correct split |
49 |
Correct |
9 ms |
10112 KB |
ok, correct split |
50 |
Correct |
8 ms |
9728 KB |
ok, no valid answer |
51 |
Correct |
6 ms |
9728 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
53 |
Correct |
12 ms |
10240 KB |
ok, no valid answer |
54 |
Correct |
10 ms |
10028 KB |
ok, no valid answer |
55 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
56 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
ok, correct split |
2 |
Correct |
7 ms |
9728 KB |
ok, correct split |
3 |
Correct |
7 ms |
9728 KB |
ok, correct split |
4 |
Correct |
7 ms |
9728 KB |
ok, correct split |
5 |
Correct |
7 ms |
9728 KB |
ok, correct split |
6 |
Correct |
7 ms |
9728 KB |
ok, correct split |
7 |
Correct |
175 ms |
27116 KB |
ok, correct split |
8 |
Correct |
154 ms |
25196 KB |
ok, correct split |
9 |
Correct |
157 ms |
24684 KB |
ok, correct split |
10 |
Correct |
147 ms |
27116 KB |
ok, correct split |
11 |
Correct |
166 ms |
26220 KB |
ok, correct split |
12 |
Correct |
7 ms |
9728 KB |
ok, correct split |
13 |
Correct |
7 ms |
9728 KB |
ok, correct split |
14 |
Correct |
7 ms |
9728 KB |
ok, correct split |
15 |
Correct |
174 ms |
23212 KB |
ok, correct split |
16 |
Correct |
133 ms |
21356 KB |
ok, correct split |
17 |
Correct |
174 ms |
27116 KB |
ok, correct split |
18 |
Correct |
165 ms |
25068 KB |
ok, correct split |
19 |
Correct |
221 ms |
25324 KB |
ok, correct split |
20 |
Correct |
168 ms |
21100 KB |
ok, correct split |
21 |
Correct |
91 ms |
21868 KB |
ok, correct split |
22 |
Correct |
93 ms |
21996 KB |
ok, correct split |
23 |
Correct |
94 ms |
21868 KB |
ok, correct split |
24 |
Correct |
7 ms |
9728 KB |
ok, correct split |
25 |
Correct |
159 ms |
21356 KB |
ok, correct split |
26 |
Correct |
45 ms |
14320 KB |
ok, correct split |
27 |
Correct |
7 ms |
9728 KB |
ok, correct split |
28 |
Correct |
164 ms |
23148 KB |
ok, correct split |
29 |
Correct |
162 ms |
23020 KB |
ok, correct split |
30 |
Correct |
169 ms |
22768 KB |
ok, correct split |
31 |
Correct |
178 ms |
23916 KB |
ok, correct split |
32 |
Correct |
173 ms |
22636 KB |
ok, correct split |
33 |
Correct |
41 ms |
13564 KB |
ok, no valid answer |
34 |
Correct |
58 ms |
15472 KB |
ok, no valid answer |
35 |
Correct |
118 ms |
21868 KB |
ok, no valid answer |
36 |
Correct |
141 ms |
21356 KB |
ok, no valid answer |
37 |
Correct |
91 ms |
21868 KB |
ok, no valid answer |
38 |
Correct |
7 ms |
9728 KB |
ok, correct split |
39 |
Correct |
8 ms |
9728 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
9728 KB |
ok, correct split |
41 |
Correct |
7 ms |
9728 KB |
ok, correct split |
42 |
Correct |
7 ms |
9728 KB |
ok, correct split |
43 |
Correct |
7 ms |
9728 KB |
ok, correct split |
44 |
Correct |
7 ms |
9728 KB |
ok, correct split |
45 |
Correct |
7 ms |
9728 KB |
ok, correct split |
46 |
Correct |
10 ms |
10112 KB |
ok, correct split |
47 |
Correct |
10 ms |
10112 KB |
ok, correct split |
48 |
Correct |
7 ms |
9728 KB |
ok, correct split |
49 |
Correct |
10 ms |
10240 KB |
ok, correct split |
50 |
Correct |
7 ms |
9728 KB |
ok, correct split |
51 |
Correct |
8 ms |
9728 KB |
ok, correct split |
52 |
Correct |
7 ms |
9728 KB |
ok, correct split |
53 |
Correct |
8 ms |
9728 KB |
ok, correct split |
54 |
Correct |
8 ms |
9728 KB |
ok, correct split |
55 |
Correct |
7 ms |
9728 KB |
ok, correct split |
56 |
Correct |
7 ms |
9728 KB |
ok, correct split |
57 |
Correct |
9 ms |
9856 KB |
ok, correct split |
58 |
Correct |
9 ms |
10112 KB |
ok, correct split |
59 |
Correct |
9 ms |
10112 KB |
ok, correct split |
60 |
Correct |
9 ms |
10112 KB |
ok, correct split |
61 |
Correct |
9 ms |
10112 KB |
ok, correct split |
62 |
Correct |
9 ms |
10112 KB |
ok, correct split |
63 |
Correct |
10 ms |
10240 KB |
ok, correct split |
64 |
Correct |
11 ms |
10240 KB |
ok, correct split |
65 |
Correct |
10 ms |
10240 KB |
ok, correct split |
66 |
Correct |
7 ms |
9728 KB |
ok, correct split |
67 |
Correct |
10 ms |
10240 KB |
ok, correct split |
68 |
Correct |
8 ms |
9856 KB |
ok, correct split |
69 |
Correct |
7 ms |
9856 KB |
ok, correct split |
70 |
Correct |
7 ms |
9728 KB |
ok, correct split |
71 |
Correct |
9 ms |
10112 KB |
ok, correct split |
72 |
Correct |
10 ms |
10112 KB |
ok, correct split |
73 |
Correct |
9 ms |
10032 KB |
ok, correct split |
74 |
Correct |
11 ms |
10240 KB |
ok, correct split |
75 |
Correct |
10 ms |
10244 KB |
ok, correct split |
76 |
Correct |
10 ms |
10240 KB |
ok, correct split |
77 |
Correct |
10 ms |
10240 KB |
ok, correct split |
78 |
Correct |
9 ms |
9976 KB |
ok, correct split |
79 |
Correct |
8 ms |
9984 KB |
ok, correct split |
80 |
Correct |
10 ms |
10240 KB |
ok, correct split |
81 |
Correct |
11 ms |
10176 KB |
ok, correct split |
82 |
Correct |
10 ms |
10240 KB |
ok, correct split |
83 |
Correct |
9 ms |
10112 KB |
ok, correct split |
84 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
85 |
Correct |
9 ms |
10112 KB |
ok, correct split |
86 |
Correct |
9 ms |
10112 KB |
ok, correct split |
87 |
Correct |
8 ms |
9728 KB |
ok, no valid answer |
88 |
Correct |
6 ms |
9728 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
90 |
Correct |
12 ms |
10240 KB |
ok, no valid answer |
91 |
Correct |
10 ms |
10028 KB |
ok, no valid answer |
92 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
93 |
Correct |
9 ms |
10112 KB |
ok, no valid answer |
94 |
Correct |
223 ms |
23916 KB |
ok, correct split |
95 |
Correct |
254 ms |
28652 KB |
ok, correct split |
96 |
Correct |
217 ms |
26348 KB |
ok, correct split |
97 |
Correct |
49 ms |
14812 KB |
ok, correct split |
98 |
Correct |
52 ms |
15088 KB |
ok, correct split |
99 |
Correct |
80 ms |
17428 KB |
ok, correct split |
100 |
Correct |
217 ms |
27884 KB |
ok, correct split |
101 |
Correct |
199 ms |
26456 KB |
ok, correct split |
102 |
Correct |
177 ms |
26348 KB |
ok, correct split |
103 |
Correct |
182 ms |
25636 KB |
ok, correct split |
104 |
Correct |
178 ms |
28396 KB |
ok, correct split |
105 |
Correct |
85 ms |
17648 KB |
ok, correct split |
106 |
Correct |
195 ms |
28016 KB |
ok, correct split |
107 |
Correct |
179 ms |
22656 KB |
ok, correct split |
108 |
Correct |
169 ms |
22508 KB |
ok, correct split |
109 |
Correct |
250 ms |
27372 KB |
ok, correct split |
110 |
Correct |
212 ms |
27756 KB |
ok, correct split |
111 |
Correct |
238 ms |
27784 KB |
ok, correct split |
112 |
Correct |
221 ms |
28000 KB |
ok, correct split |
113 |
Correct |
221 ms |
27832 KB |
ok, correct split |
114 |
Correct |
21 ms |
11776 KB |
ok, correct split |
115 |
Correct |
21 ms |
11520 KB |
ok, correct split |
116 |
Correct |
188 ms |
27756 KB |
ok, correct split |
117 |
Correct |
201 ms |
27500 KB |
ok, correct split |
118 |
Correct |
165 ms |
22380 KB |
ok, correct split |
119 |
Correct |
172 ms |
22380 KB |
ok, correct split |
120 |
Correct |
172 ms |
24684 KB |
ok, correct split |
121 |
Correct |
170 ms |
22508 KB |
ok, no valid answer |
122 |
Correct |
145 ms |
22620 KB |
ok, no valid answer |
123 |
Correct |
222 ms |
27760 KB |
ok, no valid answer |
124 |
Correct |
214 ms |
27800 KB |
ok, no valid answer |
125 |
Correct |
128 ms |
24300 KB |
ok, no valid answer |
126 |
Correct |
88 ms |
21868 KB |
ok, no valid answer |
127 |
Correct |
154 ms |
25452 KB |
ok, no valid answer |