#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 100005;
int N, M, A, B, C, sz[nmax], centroid, indx1, indx2, indx3, nrcomponente, apartinere[nmax];
vector<int> res, nod[nmax], nod_MST[nmax], O_o, componente[nmax], nod3[nmax];
bitset<nmax>viz;
void dfs(int s){
viz[s] = 1; sz[s] = 1;
for(auto it : nod[s]){
if(!viz[it]){
nod_MST[s].push_back(it);
nod_MST[it].push_back(s);
dfs(it);
sz[s] += sz[it];
}
}
}
void dfs2(int s){
viz[s] = 1; sz[s] = 1;
for(auto it : nod_MST[s]){
if(!viz[it]){
dfs2(it);
sz[s] += sz[it];
}
}
}
int findcentroid(int s, int par = 0){
for(auto it : nod_MST[s]){
if(it != par && sz[it] > (N / 2)){
return findcentroid(it, s);
}
}
return s;
}
void dfs_vanilla(int s, int par, int cock){
if(A == 0) return;
else{
res[s - 1] = cock;
A--;
for(auto it : nod_MST[s]){
if(it != par && !res[it - 1]) dfs_vanilla(it, s, cock);
}
}
}
void construct(int it){
dfs_vanilla(it, centroid, indx1);
A = B;
dfs_vanilla(centroid, 0, indx2);
for(int i=0;i<N;i++){
if(!res[i]){
res[i] = indx3;
}
}
}
void dfs_timur(int s, int par = centroid){
componente[nrcomponente].push_back(s);
apartinere[s] = nrcomponente;
for(auto it : nod_MST[s]){
if(it != par) dfs_timur(it, s);
}
}
void dfs_finala(int s){
viz[s] = 1;
for(auto it : componente[s]){
O_o.push_back(it);
}
for(auto it : nod3[s]){
if(!viz[it] && O_o.size() < A) dfs_finala(it);
}
}
void dfs_slavic(int s, int par = 0){
if(!B){
return;
}
else{
--B;
res[s - 1] = indx2;
for(auto it : nod_MST[s]){
if(it != par && !viz[it]) dfs_slavic(it, s);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n; M = p.size();
for(auto &it : p){
++it;
}
for(auto &it : q){
++it;
}
vector<pair<int,int>>tz; tz.push_back({a, 1}); tz.push_back({b, 2}); tz.push_back({c, 3});
sort(all(tz));
A = tz[0].fr; B = tz[1].fr; C = tz[2].fr;
indx1 = tz[0].sc, indx2 = tz[1].sc, indx3 = tz[2].sc;
res.resize(N);
for(int i=0;i<M;i++){
nod[p[i]].push_back(q[i]);
nod[q[i]].push_back(p[i]);
}
dfs(1);
centroid = findcentroid(1);
viz.reset();
for(int i=1;i<=n;i++) sz[i] = 0;
dfs2(centroid);
for(auto it : nod_MST[centroid]){
if(sz[it] >= A){
construct(it);
return res;
}
}
viz.reset();
for(auto it : nod_MST[centroid]){
++nrcomponente;
dfs_timur(it);
}
for(int i=1;i<=n;i++){
for(auto it : nod[i]){
if(i != centroid && it != centroid && apartinere[i] != apartinere[it]){
nod3[apartinere[i]].push_back(apartinere[it]);
nod3[apartinere[it]].push_back(apartinere[i]);
}
}
}
for(int i=1;i<=nrcomponente;i++){
if(!viz[i]){
O_o.clear();
dfs_finala(i);
if(O_o.size() >= A){
for(int i=0;i<A;i++) res[O_o[i] - 1] = indx1;
viz.reset();
for(auto it : O_o) viz[it] = 1;
dfs_slavic(centroid);
for(int i=0;i<n;i++){
if(!res[i]) res[i] = indx3;
}
return res;
}
}
}
return res;
}
Compilation message
split.cpp: In function 'void dfs_finala(int)':
split.cpp:84:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | if(!viz[it] && O_o.size() < A) dfs_finala(it);
| ~~~~~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:146:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
146 | if(O_o.size() >= A){
| ~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, correct split |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
5 ms |
9684 KB |
ok, correct split |
6 |
Correct |
5 ms |
9684 KB |
ok, correct split |
7 |
Correct |
83 ms |
26136 KB |
ok, correct split |
8 |
Correct |
90 ms |
24012 KB |
ok, correct split |
9 |
Correct |
85 ms |
23164 KB |
ok, correct split |
10 |
Correct |
85 ms |
26476 KB |
ok, correct split |
11 |
Correct |
87 ms |
26472 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, correct split |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
120 ms |
23296 KB |
ok, correct split |
5 |
Correct |
74 ms |
18892 KB |
ok, correct split |
6 |
Correct |
79 ms |
26432 KB |
ok, correct split |
7 |
Correct |
80 ms |
23572 KB |
ok, correct split |
8 |
Correct |
129 ms |
20660 KB |
ok, correct split |
9 |
Correct |
94 ms |
18760 KB |
ok, correct split |
10 |
Correct |
56 ms |
19456 KB |
ok, correct split |
11 |
Correct |
58 ms |
19448 KB |
ok, correct split |
12 |
Correct |
58 ms |
19448 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
ok, correct split |
2 |
Correct |
101 ms |
18876 KB |
ok, correct split |
3 |
Correct |
30 ms |
13396 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
91 ms |
21228 KB |
ok, correct split |
6 |
Correct |
76 ms |
20940 KB |
ok, correct split |
7 |
Correct |
76 ms |
20812 KB |
ok, correct split |
8 |
Correct |
93 ms |
22172 KB |
ok, correct split |
9 |
Correct |
80 ms |
20660 KB |
ok, correct split |
10 |
Correct |
25 ms |
13064 KB |
ok, no valid answer |
11 |
Correct |
37 ms |
14836 KB |
ok, no valid answer |
12 |
Correct |
69 ms |
21676 KB |
ok, no valid answer |
13 |
Correct |
95 ms |
20156 KB |
ok, no valid answer |
14 |
Correct |
63 ms |
22900 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
9684 KB |
ok, correct split |
4 |
Correct |
4 ms |
9684 KB |
ok, correct split |
5 |
Correct |
5 ms |
9684 KB |
ok, correct split |
6 |
Correct |
6 ms |
9684 KB |
ok, correct split |
7 |
Correct |
5 ms |
9684 KB |
ok, correct split |
8 |
Correct |
5 ms |
9684 KB |
ok, correct split |
9 |
Correct |
6 ms |
9940 KB |
ok, correct split |
10 |
Correct |
7 ms |
9940 KB |
ok, correct split |
11 |
Correct |
5 ms |
9684 KB |
ok, correct split |
12 |
Correct |
7 ms |
9940 KB |
ok, correct split |
13 |
Correct |
6 ms |
9684 KB |
ok, correct split |
14 |
Correct |
5 ms |
9684 KB |
ok, correct split |
15 |
Correct |
5 ms |
9684 KB |
ok, correct split |
16 |
Correct |
5 ms |
9684 KB |
ok, correct split |
17 |
Correct |
5 ms |
9684 KB |
ok, correct split |
18 |
Correct |
5 ms |
9684 KB |
ok, correct split |
19 |
Correct |
5 ms |
9684 KB |
ok, correct split |
20 |
Correct |
5 ms |
9772 KB |
ok, correct split |
21 |
Correct |
6 ms |
9940 KB |
ok, correct split |
22 |
Correct |
6 ms |
9940 KB |
ok, correct split |
23 |
Correct |
6 ms |
9940 KB |
ok, correct split |
24 |
Correct |
6 ms |
9940 KB |
ok, correct split |
25 |
Correct |
7 ms |
9940 KB |
ok, correct split |
26 |
Correct |
6 ms |
10172 KB |
ok, correct split |
27 |
Correct |
7 ms |
10164 KB |
ok, correct split |
28 |
Correct |
8 ms |
10100 KB |
ok, correct split |
29 |
Correct |
5 ms |
9684 KB |
ok, correct split |
30 |
Correct |
7 ms |
10032 KB |
ok, correct split |
31 |
Correct |
5 ms |
9684 KB |
ok, correct split |
32 |
Correct |
5 ms |
9684 KB |
ok, correct split |
33 |
Correct |
5 ms |
9684 KB |
ok, correct split |
34 |
Correct |
8 ms |
9976 KB |
ok, correct split |
35 |
Correct |
7 ms |
9940 KB |
ok, correct split |
36 |
Correct |
6 ms |
9940 KB |
ok, correct split |
37 |
Correct |
7 ms |
10100 KB |
ok, correct split |
38 |
Correct |
7 ms |
10096 KB |
ok, correct split |
39 |
Correct |
7 ms |
10068 KB |
ok, correct split |
40 |
Correct |
7 ms |
10032 KB |
ok, correct split |
41 |
Correct |
6 ms |
9812 KB |
ok, correct split |
42 |
Correct |
7 ms |
9840 KB |
ok, correct split |
43 |
Correct |
7 ms |
10100 KB |
ok, correct split |
44 |
Correct |
7 ms |
9972 KB |
ok, correct split |
45 |
Correct |
8 ms |
10108 KB |
ok, correct split |
46 |
Correct |
7 ms |
9972 KB |
ok, correct split |
47 |
Correct |
7 ms |
9976 KB |
ok, no valid answer |
48 |
Correct |
7 ms |
9940 KB |
ok, correct split |
49 |
Correct |
7 ms |
9972 KB |
ok, correct split |
50 |
Correct |
6 ms |
9684 KB |
ok, no valid answer |
51 |
Correct |
7 ms |
9704 KB |
ok, no valid answer |
52 |
Correct |
6 ms |
9940 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
10068 KB |
ok, no valid answer |
54 |
Correct |
6 ms |
10004 KB |
ok, no valid answer |
55 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
56 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, correct split |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
5 ms |
9684 KB |
ok, correct split |
6 |
Correct |
5 ms |
9684 KB |
ok, correct split |
7 |
Correct |
83 ms |
26136 KB |
ok, correct split |
8 |
Correct |
90 ms |
24012 KB |
ok, correct split |
9 |
Correct |
85 ms |
23164 KB |
ok, correct split |
10 |
Correct |
85 ms |
26476 KB |
ok, correct split |
11 |
Correct |
87 ms |
26472 KB |
ok, correct split |
12 |
Correct |
5 ms |
9684 KB |
ok, correct split |
13 |
Correct |
5 ms |
9684 KB |
ok, correct split |
14 |
Correct |
5 ms |
9684 KB |
ok, correct split |
15 |
Correct |
120 ms |
23296 KB |
ok, correct split |
16 |
Correct |
74 ms |
18892 KB |
ok, correct split |
17 |
Correct |
79 ms |
26432 KB |
ok, correct split |
18 |
Correct |
80 ms |
23572 KB |
ok, correct split |
19 |
Correct |
129 ms |
20660 KB |
ok, correct split |
20 |
Correct |
94 ms |
18760 KB |
ok, correct split |
21 |
Correct |
56 ms |
19456 KB |
ok, correct split |
22 |
Correct |
58 ms |
19448 KB |
ok, correct split |
23 |
Correct |
58 ms |
19448 KB |
ok, correct split |
24 |
Correct |
5 ms |
9684 KB |
ok, correct split |
25 |
Correct |
101 ms |
18876 KB |
ok, correct split |
26 |
Correct |
30 ms |
13396 KB |
ok, correct split |
27 |
Correct |
5 ms |
9684 KB |
ok, correct split |
28 |
Correct |
91 ms |
21228 KB |
ok, correct split |
29 |
Correct |
76 ms |
20940 KB |
ok, correct split |
30 |
Correct |
76 ms |
20812 KB |
ok, correct split |
31 |
Correct |
93 ms |
22172 KB |
ok, correct split |
32 |
Correct |
80 ms |
20660 KB |
ok, correct split |
33 |
Correct |
25 ms |
13064 KB |
ok, no valid answer |
34 |
Correct |
37 ms |
14836 KB |
ok, no valid answer |
35 |
Correct |
69 ms |
21676 KB |
ok, no valid answer |
36 |
Correct |
95 ms |
20156 KB |
ok, no valid answer |
37 |
Correct |
63 ms |
22900 KB |
ok, no valid answer |
38 |
Correct |
4 ms |
9684 KB |
ok, correct split |
39 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
9684 KB |
ok, correct split |
41 |
Correct |
4 ms |
9684 KB |
ok, correct split |
42 |
Correct |
5 ms |
9684 KB |
ok, correct split |
43 |
Correct |
6 ms |
9684 KB |
ok, correct split |
44 |
Correct |
5 ms |
9684 KB |
ok, correct split |
45 |
Correct |
5 ms |
9684 KB |
ok, correct split |
46 |
Correct |
6 ms |
9940 KB |
ok, correct split |
47 |
Correct |
7 ms |
9940 KB |
ok, correct split |
48 |
Correct |
5 ms |
9684 KB |
ok, correct split |
49 |
Correct |
7 ms |
9940 KB |
ok, correct split |
50 |
Correct |
6 ms |
9684 KB |
ok, correct split |
51 |
Correct |
5 ms |
9684 KB |
ok, correct split |
52 |
Correct |
5 ms |
9684 KB |
ok, correct split |
53 |
Correct |
5 ms |
9684 KB |
ok, correct split |
54 |
Correct |
5 ms |
9684 KB |
ok, correct split |
55 |
Correct |
5 ms |
9684 KB |
ok, correct split |
56 |
Correct |
5 ms |
9684 KB |
ok, correct split |
57 |
Correct |
5 ms |
9772 KB |
ok, correct split |
58 |
Correct |
6 ms |
9940 KB |
ok, correct split |
59 |
Correct |
6 ms |
9940 KB |
ok, correct split |
60 |
Correct |
6 ms |
9940 KB |
ok, correct split |
61 |
Correct |
6 ms |
9940 KB |
ok, correct split |
62 |
Correct |
7 ms |
9940 KB |
ok, correct split |
63 |
Correct |
6 ms |
10172 KB |
ok, correct split |
64 |
Correct |
7 ms |
10164 KB |
ok, correct split |
65 |
Correct |
8 ms |
10100 KB |
ok, correct split |
66 |
Correct |
5 ms |
9684 KB |
ok, correct split |
67 |
Correct |
7 ms |
10032 KB |
ok, correct split |
68 |
Correct |
5 ms |
9684 KB |
ok, correct split |
69 |
Correct |
5 ms |
9684 KB |
ok, correct split |
70 |
Correct |
5 ms |
9684 KB |
ok, correct split |
71 |
Correct |
8 ms |
9976 KB |
ok, correct split |
72 |
Correct |
7 ms |
9940 KB |
ok, correct split |
73 |
Correct |
6 ms |
9940 KB |
ok, correct split |
74 |
Correct |
7 ms |
10100 KB |
ok, correct split |
75 |
Correct |
7 ms |
10096 KB |
ok, correct split |
76 |
Correct |
7 ms |
10068 KB |
ok, correct split |
77 |
Correct |
7 ms |
10032 KB |
ok, correct split |
78 |
Correct |
6 ms |
9812 KB |
ok, correct split |
79 |
Correct |
7 ms |
9840 KB |
ok, correct split |
80 |
Correct |
7 ms |
10100 KB |
ok, correct split |
81 |
Correct |
7 ms |
9972 KB |
ok, correct split |
82 |
Correct |
8 ms |
10108 KB |
ok, correct split |
83 |
Correct |
7 ms |
9972 KB |
ok, correct split |
84 |
Correct |
7 ms |
9976 KB |
ok, no valid answer |
85 |
Correct |
7 ms |
9940 KB |
ok, correct split |
86 |
Correct |
7 ms |
9972 KB |
ok, correct split |
87 |
Correct |
6 ms |
9684 KB |
ok, no valid answer |
88 |
Correct |
7 ms |
9704 KB |
ok, no valid answer |
89 |
Correct |
6 ms |
9940 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
10068 KB |
ok, no valid answer |
91 |
Correct |
6 ms |
10004 KB |
ok, no valid answer |
92 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
93 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
94 |
Correct |
87 ms |
22780 KB |
ok, correct split |
95 |
Correct |
125 ms |
27856 KB |
ok, correct split |
96 |
Correct |
100 ms |
26164 KB |
ok, correct split |
97 |
Correct |
30 ms |
13772 KB |
ok, correct split |
98 |
Correct |
29 ms |
13928 KB |
ok, correct split |
99 |
Correct |
53 ms |
16100 KB |
ok, correct split |
100 |
Correct |
109 ms |
23532 KB |
ok, correct split |
101 |
Correct |
102 ms |
22492 KB |
ok, correct split |
102 |
Correct |
108 ms |
22120 KB |
ok, correct split |
103 |
Correct |
88 ms |
22048 KB |
ok, correct split |
104 |
Correct |
91 ms |
23784 KB |
ok, correct split |
105 |
Correct |
53 ms |
17228 KB |
ok, correct split |
106 |
Correct |
130 ms |
31456 KB |
ok, correct split |
107 |
Correct |
80 ms |
21212 KB |
ok, correct split |
108 |
Correct |
99 ms |
21096 KB |
ok, correct split |
109 |
Correct |
126 ms |
24100 KB |
ok, correct split |
110 |
Correct |
114 ms |
26104 KB |
ok, correct split |
111 |
Correct |
123 ms |
25896 KB |
ok, correct split |
112 |
Correct |
123 ms |
26484 KB |
ok, correct split |
113 |
Correct |
122 ms |
26096 KB |
ok, correct split |
114 |
Correct |
15 ms |
11348 KB |
ok, correct split |
115 |
Correct |
14 ms |
11124 KB |
ok, correct split |
116 |
Correct |
130 ms |
25704 KB |
ok, correct split |
117 |
Correct |
109 ms |
25280 KB |
ok, correct split |
118 |
Correct |
81 ms |
19880 KB |
ok, correct split |
119 |
Correct |
98 ms |
19820 KB |
ok, correct split |
120 |
Correct |
81 ms |
24024 KB |
ok, correct split |
121 |
Correct |
106 ms |
20860 KB |
ok, no valid answer |
122 |
Correct |
77 ms |
21644 KB |
ok, no valid answer |
123 |
Correct |
116 ms |
24660 KB |
ok, no valid answer |
124 |
Correct |
117 ms |
24524 KB |
ok, no valid answer |
125 |
Correct |
78 ms |
23880 KB |
ok, no valid answer |
126 |
Correct |
57 ms |
22656 KB |
ok, no valid answer |
127 |
Correct |
92 ms |
23652 KB |
ok, no valid answer |