#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m, k, id[N], siz[N], rt;
vector<int> adj[N], tadj[N], nadj[N], comps[N], orda;
vector<pair<int, int>> bruh;
bool vis[N];
void get_tree(int v){
vis[v] = 1; siz[v] = 1;
for(auto u : adj[v])
if(!vis[u]) tadj[v].push_back(u), tadj[u].push_back(v), get_tree(u), siz[v] += siz[u];
}
int get_centroid(){
int p = -1, v = 0;
do{
int nxt = -1;
for(auto u : tadj[v])
if(u!=p && 2*siz[u]>n) nxt = u;
p = v, v = nxt;
} while(~v);
return p;
}
void get_label(int v, int p, int idx){
comps[idx].push_back(v);
id[v] = idx;
for(auto u : tadj[v])
if(u!=p) get_label(u, v, idx);
}
void get_orda(int v){
vis[v] = 1;
orda.push_back(v);
for(auto u : adj[v])
if(!vis[u]) get_orda(u);
}
vector<int> get_ans(vector<int> a0){
memset(vis, 0, sizeof vis);
for(auto x : a0) vis[x] = 1;
for(int i = 0; i<n; ++i)
if(!vis[i]){get_orda(i); break;}
vector<int> ans(n, bruh[2].second);
while((int)a0.size()>bruh[0].first) orda.push_back(a0.back()), a0.pop_back();
for(auto x : a0)
ans[x] = bruh[0].second;
for(int i = 0; i<bruh[1].first; ++i)
ans[orda[i]] = bruh[1].second;
return ans;
}
bool find_good(int v, int& cur){
vis[v] = 1; cur += comps[v].size();
orda.push_back(v);
if(cur>=bruh[0].first) return 1;
for(auto u : nadj[v])
if(!vis[u]){
bool tmp = find_good(u, cur);
if(tmp) return 1;
}
return 0;
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){
n = _n, m = _p.size();
bruh.push_back({_a, 1});
bruh.push_back({_b, 2});
bruh.push_back({_c, 3});
sort(bruh.begin(), bruh.end());
for(int i = 0; i<m; ++i)
adj[_p[i]].push_back(_q[i]), adj[_q[i]].push_back(_p[i]);
get_tree(0);
rt = get_centroid(); k = tadj[rt].size();
for(int i = 0; i<k; ++i)
get_label(tadj[rt][i], rt, i);
id[rt] = -1;
for(int i = 0; i<k; ++i)
if((int)comps[i].size()>=bruh[0].first)
return get_ans(comps[i]);
for(int i = 0; i<m; ++i){
int u = id[_p[i]], v = id[_q[i]];
if(u==v || u==-1 || v==-1) continue;
nadj[u].push_back(v);
nadj[v].push_back(u);
} memset(vis, 0, sizeof vis);
for(int i = 0; i<k; ++i){
if(vis[i]) continue;
int tot = 0;
if(find_good(i, tot)){
vector<int> a0;
for(auto x : orda)
a0.insert(a0.end(), comps[x].begin(), comps[x].end());
orda.clear(); return get_ans(a0);
} else{
orda.clear();
}
}
vector<int> ans(n, 0);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19276 KB |
ok, correct split |
2 |
Correct |
11 ms |
19276 KB |
ok, correct split |
3 |
Correct |
10 ms |
19276 KB |
ok, correct split |
4 |
Correct |
10 ms |
19276 KB |
ok, correct split |
5 |
Correct |
11 ms |
19276 KB |
ok, correct split |
6 |
Correct |
11 ms |
19180 KB |
ok, correct split |
7 |
Correct |
105 ms |
36876 KB |
ok, correct split |
8 |
Correct |
136 ms |
34700 KB |
ok, correct split |
9 |
Correct |
111 ms |
34076 KB |
ok, correct split |
10 |
Correct |
109 ms |
37312 KB |
ok, correct split |
11 |
Correct |
105 ms |
37308 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19276 KB |
ok, correct split |
2 |
Correct |
13 ms |
19288 KB |
ok, correct split |
3 |
Correct |
11 ms |
19276 KB |
ok, correct split |
4 |
Correct |
136 ms |
34100 KB |
ok, correct split |
5 |
Correct |
93 ms |
29464 KB |
ok, correct split |
6 |
Correct |
110 ms |
37312 KB |
ok, correct split |
7 |
Correct |
112 ms |
34400 KB |
ok, correct split |
8 |
Correct |
148 ms |
31340 KB |
ok, correct split |
9 |
Correct |
102 ms |
29284 KB |
ok, correct split |
10 |
Correct |
74 ms |
32700 KB |
ok, correct split |
11 |
Correct |
88 ms |
32672 KB |
ok, correct split |
12 |
Correct |
80 ms |
32648 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19276 KB |
ok, correct split |
2 |
Correct |
101 ms |
29452 KB |
ok, correct split |
3 |
Correct |
40 ms |
23360 KB |
ok, correct split |
4 |
Correct |
11 ms |
19252 KB |
ok, correct split |
5 |
Correct |
117 ms |
31756 KB |
ok, correct split |
6 |
Correct |
102 ms |
31548 KB |
ok, correct split |
7 |
Correct |
102 ms |
31264 KB |
ok, correct split |
8 |
Correct |
111 ms |
32660 KB |
ok, correct split |
9 |
Correct |
111 ms |
31108 KB |
ok, correct split |
10 |
Correct |
39 ms |
22520 KB |
ok, no valid answer |
11 |
Correct |
50 ms |
24120 KB |
ok, no valid answer |
12 |
Correct |
110 ms |
30784 KB |
ok, no valid answer |
13 |
Correct |
94 ms |
29220 KB |
ok, no valid answer |
14 |
Correct |
75 ms |
32124 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
19276 KB |
ok, correct split |
2 |
Correct |
10 ms |
19276 KB |
ok, no valid answer |
3 |
Correct |
10 ms |
19276 KB |
ok, correct split |
4 |
Correct |
10 ms |
19276 KB |
ok, correct split |
5 |
Correct |
10 ms |
19276 KB |
ok, correct split |
6 |
Correct |
10 ms |
19276 KB |
ok, correct split |
7 |
Correct |
11 ms |
19276 KB |
ok, correct split |
8 |
Correct |
13 ms |
19276 KB |
ok, correct split |
9 |
Correct |
13 ms |
19548 KB |
ok, correct split |
10 |
Correct |
13 ms |
19532 KB |
ok, correct split |
11 |
Correct |
12 ms |
19276 KB |
ok, correct split |
12 |
Correct |
12 ms |
19532 KB |
ok, correct split |
13 |
Correct |
10 ms |
19276 KB |
ok, correct split |
14 |
Correct |
12 ms |
19276 KB |
ok, correct split |
15 |
Correct |
11 ms |
19232 KB |
ok, correct split |
16 |
Correct |
12 ms |
19216 KB |
ok, correct split |
17 |
Correct |
10 ms |
19276 KB |
ok, correct split |
18 |
Correct |
12 ms |
19272 KB |
ok, correct split |
19 |
Correct |
12 ms |
19276 KB |
ok, correct split |
20 |
Correct |
11 ms |
19404 KB |
ok, correct split |
21 |
Correct |
12 ms |
19532 KB |
ok, correct split |
22 |
Correct |
12 ms |
19532 KB |
ok, correct split |
23 |
Correct |
12 ms |
19532 KB |
ok, correct split |
24 |
Correct |
17 ms |
19604 KB |
ok, correct split |
25 |
Correct |
12 ms |
19532 KB |
ok, correct split |
26 |
Correct |
12 ms |
19660 KB |
ok, correct split |
27 |
Correct |
13 ms |
19808 KB |
ok, correct split |
28 |
Correct |
13 ms |
19704 KB |
ok, correct split |
29 |
Correct |
11 ms |
19276 KB |
ok, correct split |
30 |
Correct |
14 ms |
19660 KB |
ok, correct split |
31 |
Correct |
11 ms |
19280 KB |
ok, correct split |
32 |
Correct |
10 ms |
19216 KB |
ok, correct split |
33 |
Correct |
11 ms |
19276 KB |
ok, correct split |
34 |
Correct |
14 ms |
19528 KB |
ok, correct split |
35 |
Correct |
13 ms |
19612 KB |
ok, correct split |
36 |
Correct |
12 ms |
19484 KB |
ok, correct split |
37 |
Correct |
12 ms |
19668 KB |
ok, correct split |
38 |
Correct |
13 ms |
19660 KB |
ok, correct split |
39 |
Correct |
14 ms |
19664 KB |
ok, correct split |
40 |
Correct |
13 ms |
19532 KB |
ok, correct split |
41 |
Correct |
12 ms |
19404 KB |
ok, correct split |
42 |
Correct |
11 ms |
19356 KB |
ok, correct split |
43 |
Correct |
13 ms |
19676 KB |
ok, correct split |
44 |
Correct |
14 ms |
19532 KB |
ok, correct split |
45 |
Correct |
12 ms |
19680 KB |
ok, correct split |
46 |
Correct |
12 ms |
19532 KB |
ok, correct split |
47 |
Correct |
12 ms |
19532 KB |
ok, no valid answer |
48 |
Correct |
12 ms |
19532 KB |
ok, correct split |
49 |
Correct |
12 ms |
19684 KB |
ok, correct split |
50 |
Correct |
11 ms |
19264 KB |
ok, no valid answer |
51 |
Correct |
10 ms |
19276 KB |
ok, no valid answer |
52 |
Correct |
12 ms |
19532 KB |
ok, no valid answer |
53 |
Correct |
13 ms |
19532 KB |
ok, no valid answer |
54 |
Correct |
13 ms |
19532 KB |
ok, no valid answer |
55 |
Correct |
12 ms |
19532 KB |
ok, no valid answer |
56 |
Correct |
13 ms |
19564 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19276 KB |
ok, correct split |
2 |
Correct |
11 ms |
19276 KB |
ok, correct split |
3 |
Correct |
10 ms |
19276 KB |
ok, correct split |
4 |
Correct |
10 ms |
19276 KB |
ok, correct split |
5 |
Correct |
11 ms |
19276 KB |
ok, correct split |
6 |
Correct |
11 ms |
19180 KB |
ok, correct split |
7 |
Correct |
105 ms |
36876 KB |
ok, correct split |
8 |
Correct |
136 ms |
34700 KB |
ok, correct split |
9 |
Correct |
111 ms |
34076 KB |
ok, correct split |
10 |
Correct |
109 ms |
37312 KB |
ok, correct split |
11 |
Correct |
105 ms |
37308 KB |
ok, correct split |
12 |
Correct |
10 ms |
19276 KB |
ok, correct split |
13 |
Correct |
13 ms |
19288 KB |
ok, correct split |
14 |
Correct |
11 ms |
19276 KB |
ok, correct split |
15 |
Correct |
136 ms |
34100 KB |
ok, correct split |
16 |
Correct |
93 ms |
29464 KB |
ok, correct split |
17 |
Correct |
110 ms |
37312 KB |
ok, correct split |
18 |
Correct |
112 ms |
34400 KB |
ok, correct split |
19 |
Correct |
148 ms |
31340 KB |
ok, correct split |
20 |
Correct |
102 ms |
29284 KB |
ok, correct split |
21 |
Correct |
74 ms |
32700 KB |
ok, correct split |
22 |
Correct |
88 ms |
32672 KB |
ok, correct split |
23 |
Correct |
80 ms |
32648 KB |
ok, correct split |
24 |
Correct |
10 ms |
19276 KB |
ok, correct split |
25 |
Correct |
101 ms |
29452 KB |
ok, correct split |
26 |
Correct |
40 ms |
23360 KB |
ok, correct split |
27 |
Correct |
11 ms |
19252 KB |
ok, correct split |
28 |
Correct |
117 ms |
31756 KB |
ok, correct split |
29 |
Correct |
102 ms |
31548 KB |
ok, correct split |
30 |
Correct |
102 ms |
31264 KB |
ok, correct split |
31 |
Correct |
111 ms |
32660 KB |
ok, correct split |
32 |
Correct |
111 ms |
31108 KB |
ok, correct split |
33 |
Correct |
39 ms |
22520 KB |
ok, no valid answer |
34 |
Correct |
50 ms |
24120 KB |
ok, no valid answer |
35 |
Correct |
110 ms |
30784 KB |
ok, no valid answer |
36 |
Correct |
94 ms |
29220 KB |
ok, no valid answer |
37 |
Correct |
75 ms |
32124 KB |
ok, no valid answer |
38 |
Correct |
11 ms |
19276 KB |
ok, correct split |
39 |
Correct |
10 ms |
19276 KB |
ok, no valid answer |
40 |
Correct |
10 ms |
19276 KB |
ok, correct split |
41 |
Correct |
10 ms |
19276 KB |
ok, correct split |
42 |
Correct |
10 ms |
19276 KB |
ok, correct split |
43 |
Correct |
10 ms |
19276 KB |
ok, correct split |
44 |
Correct |
11 ms |
19276 KB |
ok, correct split |
45 |
Correct |
13 ms |
19276 KB |
ok, correct split |
46 |
Correct |
13 ms |
19548 KB |
ok, correct split |
47 |
Correct |
13 ms |
19532 KB |
ok, correct split |
48 |
Correct |
12 ms |
19276 KB |
ok, correct split |
49 |
Correct |
12 ms |
19532 KB |
ok, correct split |
50 |
Correct |
10 ms |
19276 KB |
ok, correct split |
51 |
Correct |
12 ms |
19276 KB |
ok, correct split |
52 |
Correct |
11 ms |
19232 KB |
ok, correct split |
53 |
Correct |
12 ms |
19216 KB |
ok, correct split |
54 |
Correct |
10 ms |
19276 KB |
ok, correct split |
55 |
Correct |
12 ms |
19272 KB |
ok, correct split |
56 |
Correct |
12 ms |
19276 KB |
ok, correct split |
57 |
Correct |
11 ms |
19404 KB |
ok, correct split |
58 |
Correct |
12 ms |
19532 KB |
ok, correct split |
59 |
Correct |
12 ms |
19532 KB |
ok, correct split |
60 |
Correct |
12 ms |
19532 KB |
ok, correct split |
61 |
Correct |
17 ms |
19604 KB |
ok, correct split |
62 |
Correct |
12 ms |
19532 KB |
ok, correct split |
63 |
Correct |
12 ms |
19660 KB |
ok, correct split |
64 |
Correct |
13 ms |
19808 KB |
ok, correct split |
65 |
Correct |
13 ms |
19704 KB |
ok, correct split |
66 |
Correct |
11 ms |
19276 KB |
ok, correct split |
67 |
Correct |
14 ms |
19660 KB |
ok, correct split |
68 |
Correct |
11 ms |
19280 KB |
ok, correct split |
69 |
Correct |
10 ms |
19216 KB |
ok, correct split |
70 |
Correct |
11 ms |
19276 KB |
ok, correct split |
71 |
Correct |
14 ms |
19528 KB |
ok, correct split |
72 |
Correct |
13 ms |
19612 KB |
ok, correct split |
73 |
Correct |
12 ms |
19484 KB |
ok, correct split |
74 |
Correct |
12 ms |
19668 KB |
ok, correct split |
75 |
Correct |
13 ms |
19660 KB |
ok, correct split |
76 |
Correct |
14 ms |
19664 KB |
ok, correct split |
77 |
Correct |
13 ms |
19532 KB |
ok, correct split |
78 |
Correct |
12 ms |
19404 KB |
ok, correct split |
79 |
Correct |
11 ms |
19356 KB |
ok, correct split |
80 |
Correct |
13 ms |
19676 KB |
ok, correct split |
81 |
Correct |
14 ms |
19532 KB |
ok, correct split |
82 |
Correct |
12 ms |
19680 KB |
ok, correct split |
83 |
Correct |
12 ms |
19532 KB |
ok, correct split |
84 |
Correct |
12 ms |
19532 KB |
ok, no valid answer |
85 |
Correct |
12 ms |
19532 KB |
ok, correct split |
86 |
Correct |
12 ms |
19684 KB |
ok, correct split |
87 |
Correct |
11 ms |
19264 KB |
ok, no valid answer |
88 |
Correct |
10 ms |
19276 KB |
ok, no valid answer |
89 |
Correct |
12 ms |
19532 KB |
ok, no valid answer |
90 |
Correct |
13 ms |
19532 KB |
ok, no valid answer |
91 |
Correct |
13 ms |
19532 KB |
ok, no valid answer |
92 |
Correct |
12 ms |
19532 KB |
ok, no valid answer |
93 |
Correct |
13 ms |
19564 KB |
ok, no valid answer |
94 |
Correct |
110 ms |
33664 KB |
ok, correct split |
95 |
Correct |
154 ms |
38632 KB |
ok, correct split |
96 |
Correct |
142 ms |
37060 KB |
ok, correct split |
97 |
Correct |
40 ms |
23864 KB |
ok, correct split |
98 |
Correct |
44 ms |
23964 KB |
ok, correct split |
99 |
Correct |
62 ms |
26068 KB |
ok, correct split |
100 |
Correct |
140 ms |
34076 KB |
ok, correct split |
101 |
Correct |
133 ms |
33104 KB |
ok, correct split |
102 |
Correct |
117 ms |
33344 KB |
ok, correct split |
103 |
Correct |
109 ms |
33384 KB |
ok, correct split |
104 |
Correct |
111 ms |
34324 KB |
ok, correct split |
105 |
Correct |
61 ms |
26820 KB |
ok, correct split |
106 |
Correct |
134 ms |
40780 KB |
ok, correct split |
107 |
Correct |
96 ms |
30836 KB |
ok, correct split |
108 |
Correct |
96 ms |
30600 KB |
ok, correct split |
109 |
Correct |
140 ms |
33656 KB |
ok, correct split |
110 |
Correct |
135 ms |
34636 KB |
ok, correct split |
111 |
Correct |
134 ms |
34700 KB |
ok, correct split |
112 |
Correct |
133 ms |
34976 KB |
ok, correct split |
113 |
Correct |
128 ms |
34712 KB |
ok, correct split |
114 |
Correct |
21 ms |
21068 KB |
ok, correct split |
115 |
Correct |
20 ms |
20892 KB |
ok, correct split |
116 |
Correct |
145 ms |
34572 KB |
ok, correct split |
117 |
Correct |
145 ms |
34304 KB |
ok, correct split |
118 |
Correct |
101 ms |
30704 KB |
ok, correct split |
119 |
Correct |
103 ms |
30384 KB |
ok, correct split |
120 |
Correct |
113 ms |
34632 KB |
ok, correct split |
121 |
Correct |
91 ms |
30020 KB |
ok, no valid answer |
122 |
Correct |
94 ms |
30712 KB |
ok, no valid answer |
123 |
Correct |
132 ms |
33756 KB |
ok, no valid answer |
124 |
Correct |
137 ms |
33604 KB |
ok, no valid answer |
125 |
Correct |
95 ms |
33140 KB |
ok, no valid answer |
126 |
Correct |
68 ms |
31832 KB |
ok, no valid answer |
127 |
Correct |
104 ms |
32916 KB |
ok, no valid answer |