#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define MOD 998244353
vector<int> adj[100000], adj3[100000], grpv[100001];
set<pair<int, tuple<int, int, int>>> adj2[100000];
vector<int> path, res;
vector<pair<int, int>> t1;
int sz[100000], grp[100001], d, e, c1 = -1, c2 = -1, cnt, csz;
bool v[100000];
int size(int x, int g) {
v[x] = 1; sz[x] = 1; grp[x] = g;
if(g != -1) grpv[g].push_back(x);
for(int i : adj3[x]) if(!v[i]) {
if(g == -1) sz[x] += size(i, i);
else sz[x] += size(i, g);
}
return sz[x];
}
int centroid(int x, int n) {
v[x] = 1;
for(int i : adj3[x]) if(!v[i] && sz[i] > n/2) return centroid(i, n);
return x;
}
bool dfs(int x, int _c1, int _c2) {
v[x] = 1;
path.push_back(x);
if(csz >= d) {
c1 = _c1; c2 = _c2;
return true;
}
for(auto i : adj2[x]) if(!v[i.first]) {
csz += get<0>(i.second);
if(dfs(i.first, get<1>(i.second), get<2>(i.second))) return true;
}
return false;
}
void dfs2(int x) {
v[x] = 1;
if(cnt == 0) return;
res[x] = t1[0].second;
cnt--;
for(int i : adj[x]) if(!v[i] && grp[i] == grp[x]) dfs2(i);
}
void dfs3(int x) {
if(cnt == 0) return;
res[x] = t1[1].second;
cnt--;
for(int i : adj[x]) if(res[i] == 0) dfs3(i);
}
int up[100000];
int root(int x) {
if(up[x] == x) return x;
else return up[x] = root(up[x]);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for(int i = 0; i < n; i++) res.push_back(0);
for(int i = 0; i < n; i++) up[i] = i;
for(int i = 0; i < p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
if(root(p[i]) == root(q[i])) continue;
int x = root(p[i]), y = root(q[i]);
up[x] = y;
adj3[p[i]].push_back(q[i]);
adj3[q[i]].push_back(p[i]);
}
t1 = {{a, 1}, {b, 2}, {c, 3}};
sort(t1.begin(), t1.end());
d = t1[0].first; e = t1[1].first;
size(0, n);
memset(v, 0, sizeof(v));
int cen = centroid(0, n);
memset(v, 0, sizeof(v));
size(cen, -1);
for(int i : adj3[cen]) if(sz[i] >= d) {
memset(v, 0, sizeof(v));
cnt = d;
dfs2(i);
cnt = e;
dfs3(cen);
for(int j = 0; j < n; j++) if(res[j] == 0) res[j] = t1[2].second;
return res;
}
for(int i : adj3[cen]) assert(sz[i] == grpv[i].size());
for(int i = 0; i < n; i++) {
for(int j : adj[i]) {
if(grp[i] == -1 || grp[j] == -1) continue;
if(grp[i] == grp[j]) continue;
auto it = adj2[grp[i]].lower_bound({grp[j], {0, 0, 0}});
if(it != adj2[grp[i]].end() && it->first == grp[j]) continue;
adj2[grp[i]].insert({grp[j], {sz[grp[j]], i, j}});
adj2[grp[j]].insert({grp[i], {sz[grp[i]], j, i}});
}
}
memset(v, 0, sizeof(v));
for(int i : adj3[cen]) if(!v[i]) {
csz = sz[i]; path.clear();
if(dfs(i, -1, -1)) break;
}
if(c1 == -1) return res;
cnt = d;
for(int i = 0; i < path.size()-1; i++) {
for(int j : grpv[path[i]]) {
res[j] = t1[0].second;
cnt--;
}
}
memset(v, 0, sizeof(v));
dfs2(c2);
cnt = e;
dfs3(cen);
for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = t1[2].second;
return res;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < p.size(); i++) {
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from split.cpp:1:
split.cpp:93:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i : adj3[cen]) assert(sz[i] == grpv[i].size());
| ~~~~~~^~~~~~~~~~~~~~~~~
split.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 0; i < path.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
13148 KB |
ok, correct split |
2 |
Correct |
3 ms |
13148 KB |
ok, correct split |
3 |
Correct |
3 ms |
13148 KB |
ok, correct split |
4 |
Correct |
3 ms |
13148 KB |
ok, correct split |
5 |
Correct |
3 ms |
13148 KB |
ok, correct split |
6 |
Correct |
3 ms |
13148 KB |
ok, correct split |
7 |
Correct |
84 ms |
29000 KB |
ok, correct split |
8 |
Correct |
77 ms |
27212 KB |
ok, correct split |
9 |
Correct |
82 ms |
26436 KB |
ok, correct split |
10 |
Correct |
82 ms |
29000 KB |
ok, correct split |
11 |
Correct |
81 ms |
27976 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13148 KB |
ok, correct split |
2 |
Correct |
3 ms |
13148 KB |
ok, correct split |
3 |
Correct |
3 ms |
13148 KB |
ok, correct split |
4 |
Correct |
85 ms |
24072 KB |
ok, correct split |
5 |
Correct |
72 ms |
23120 KB |
ok, correct split |
6 |
Correct |
74 ms |
29000 KB |
ok, correct split |
7 |
Correct |
80 ms |
26956 KB |
ok, correct split |
8 |
Correct |
93 ms |
25160 KB |
ok, correct split |
9 |
Correct |
68 ms |
23116 KB |
ok, correct split |
10 |
Correct |
56 ms |
26196 KB |
ok, correct split |
11 |
Correct |
57 ms |
26356 KB |
ok, correct split |
12 |
Correct |
57 ms |
26356 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13144 KB |
ok, correct split |
2 |
Correct |
83 ms |
23020 KB |
ok, correct split |
3 |
Correct |
24 ms |
17236 KB |
ok, correct split |
4 |
Correct |
3 ms |
13148 KB |
ok, correct split |
5 |
Correct |
73 ms |
24960 KB |
ok, correct split |
6 |
Correct |
69 ms |
24648 KB |
ok, correct split |
7 |
Correct |
77 ms |
24652 KB |
ok, correct split |
8 |
Correct |
72 ms |
25672 KB |
ok, correct split |
9 |
Correct |
74 ms |
24740 KB |
ok, correct split |
10 |
Correct |
22 ms |
16596 KB |
ok, no valid answer |
11 |
Correct |
36 ms |
18540 KB |
ok, no valid answer |
12 |
Correct |
65 ms |
25048 KB |
ok, no valid answer |
13 |
Correct |
71 ms |
23372 KB |
ok, no valid answer |
14 |
Correct |
63 ms |
26188 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13148 KB |
ok, correct split |
2 |
Correct |
2 ms |
13144 KB |
ok, no valid answer |
3 |
Correct |
3 ms |
13148 KB |
ok, correct split |
4 |
Correct |
3 ms |
13260 KB |
ok, correct split |
5 |
Correct |
3 ms |
13400 KB |
ok, correct split |
6 |
Correct |
2 ms |
13148 KB |
ok, correct split |
7 |
Correct |
2 ms |
13148 KB |
ok, correct split |
8 |
Correct |
3 ms |
13148 KB |
ok, correct split |
9 |
Correct |
5 ms |
13488 KB |
ok, correct split |
10 |
Correct |
4 ms |
13404 KB |
ok, correct split |
11 |
Correct |
3 ms |
13148 KB |
ok, correct split |
12 |
Correct |
4 ms |
13660 KB |
ok, correct split |
13 |
Correct |
3 ms |
13148 KB |
ok, correct split |
14 |
Correct |
3 ms |
13148 KB |
ok, correct split |
15 |
Correct |
3 ms |
13148 KB |
ok, correct split |
16 |
Correct |
3 ms |
13148 KB |
ok, correct split |
17 |
Correct |
3 ms |
13148 KB |
ok, correct split |
18 |
Correct |
3 ms |
13144 KB |
ok, correct split |
19 |
Correct |
3 ms |
13148 KB |
ok, correct split |
20 |
Correct |
3 ms |
13404 KB |
ok, correct split |
21 |
Correct |
4 ms |
13404 KB |
ok, correct split |
22 |
Correct |
4 ms |
13404 KB |
ok, correct split |
23 |
Correct |
4 ms |
13404 KB |
ok, correct split |
24 |
Correct |
4 ms |
13556 KB |
ok, correct split |
25 |
Correct |
4 ms |
13404 KB |
ok, correct split |
26 |
Correct |
4 ms |
13660 KB |
ok, correct split |
27 |
Correct |
5 ms |
13660 KB |
ok, correct split |
28 |
Correct |
4 ms |
13516 KB |
ok, correct split |
29 |
Correct |
3 ms |
13144 KB |
ok, correct split |
30 |
Correct |
4 ms |
13660 KB |
ok, correct split |
31 |
Correct |
3 ms |
13148 KB |
ok, correct split |
32 |
Correct |
3 ms |
13148 KB |
ok, correct split |
33 |
Correct |
3 ms |
13148 KB |
ok, correct split |
34 |
Correct |
4 ms |
13400 KB |
ok, correct split |
35 |
Correct |
4 ms |
13404 KB |
ok, correct split |
36 |
Correct |
4 ms |
13520 KB |
ok, correct split |
37 |
Correct |
5 ms |
13660 KB |
ok, correct split |
38 |
Correct |
5 ms |
13660 KB |
ok, correct split |
39 |
Correct |
5 ms |
13660 KB |
ok, correct split |
40 |
Correct |
5 ms |
13660 KB |
ok, correct split |
41 |
Correct |
5 ms |
13320 KB |
ok, correct split |
42 |
Correct |
4 ms |
13404 KB |
ok, correct split |
43 |
Correct |
5 ms |
13660 KB |
ok, correct split |
44 |
Correct |
4 ms |
13660 KB |
ok, correct split |
45 |
Correct |
5 ms |
13660 KB |
ok, correct split |
46 |
Correct |
4 ms |
13404 KB |
ok, correct split |
47 |
Correct |
4 ms |
13404 KB |
ok, no valid answer |
48 |
Correct |
4 ms |
13572 KB |
ok, correct split |
49 |
Correct |
4 ms |
13404 KB |
ok, correct split |
50 |
Correct |
3 ms |
13148 KB |
ok, no valid answer |
51 |
Correct |
3 ms |
13148 KB |
ok, no valid answer |
52 |
Correct |
4 ms |
13404 KB |
ok, no valid answer |
53 |
Correct |
5 ms |
13404 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
13660 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
13656 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
13660 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
13148 KB |
ok, correct split |
2 |
Correct |
3 ms |
13148 KB |
ok, correct split |
3 |
Correct |
3 ms |
13148 KB |
ok, correct split |
4 |
Correct |
3 ms |
13148 KB |
ok, correct split |
5 |
Correct |
3 ms |
13148 KB |
ok, correct split |
6 |
Correct |
3 ms |
13148 KB |
ok, correct split |
7 |
Correct |
84 ms |
29000 KB |
ok, correct split |
8 |
Correct |
77 ms |
27212 KB |
ok, correct split |
9 |
Correct |
82 ms |
26436 KB |
ok, correct split |
10 |
Correct |
82 ms |
29000 KB |
ok, correct split |
11 |
Correct |
81 ms |
27976 KB |
ok, correct split |
12 |
Correct |
3 ms |
13148 KB |
ok, correct split |
13 |
Correct |
3 ms |
13148 KB |
ok, correct split |
14 |
Correct |
3 ms |
13148 KB |
ok, correct split |
15 |
Correct |
85 ms |
24072 KB |
ok, correct split |
16 |
Correct |
72 ms |
23120 KB |
ok, correct split |
17 |
Correct |
74 ms |
29000 KB |
ok, correct split |
18 |
Correct |
80 ms |
26956 KB |
ok, correct split |
19 |
Correct |
93 ms |
25160 KB |
ok, correct split |
20 |
Correct |
68 ms |
23116 KB |
ok, correct split |
21 |
Correct |
56 ms |
26196 KB |
ok, correct split |
22 |
Correct |
57 ms |
26356 KB |
ok, correct split |
23 |
Correct |
57 ms |
26356 KB |
ok, correct split |
24 |
Correct |
3 ms |
13144 KB |
ok, correct split |
25 |
Correct |
83 ms |
23020 KB |
ok, correct split |
26 |
Correct |
24 ms |
17236 KB |
ok, correct split |
27 |
Correct |
3 ms |
13148 KB |
ok, correct split |
28 |
Correct |
73 ms |
24960 KB |
ok, correct split |
29 |
Correct |
69 ms |
24648 KB |
ok, correct split |
30 |
Correct |
77 ms |
24652 KB |
ok, correct split |
31 |
Correct |
72 ms |
25672 KB |
ok, correct split |
32 |
Correct |
74 ms |
24740 KB |
ok, correct split |
33 |
Correct |
22 ms |
16596 KB |
ok, no valid answer |
34 |
Correct |
36 ms |
18540 KB |
ok, no valid answer |
35 |
Correct |
65 ms |
25048 KB |
ok, no valid answer |
36 |
Correct |
71 ms |
23372 KB |
ok, no valid answer |
37 |
Correct |
63 ms |
26188 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
13148 KB |
ok, correct split |
39 |
Correct |
2 ms |
13144 KB |
ok, no valid answer |
40 |
Correct |
3 ms |
13148 KB |
ok, correct split |
41 |
Correct |
3 ms |
13260 KB |
ok, correct split |
42 |
Correct |
3 ms |
13400 KB |
ok, correct split |
43 |
Correct |
2 ms |
13148 KB |
ok, correct split |
44 |
Correct |
2 ms |
13148 KB |
ok, correct split |
45 |
Correct |
3 ms |
13148 KB |
ok, correct split |
46 |
Correct |
5 ms |
13488 KB |
ok, correct split |
47 |
Correct |
4 ms |
13404 KB |
ok, correct split |
48 |
Correct |
3 ms |
13148 KB |
ok, correct split |
49 |
Correct |
4 ms |
13660 KB |
ok, correct split |
50 |
Correct |
3 ms |
13148 KB |
ok, correct split |
51 |
Correct |
3 ms |
13148 KB |
ok, correct split |
52 |
Correct |
3 ms |
13148 KB |
ok, correct split |
53 |
Correct |
3 ms |
13148 KB |
ok, correct split |
54 |
Correct |
3 ms |
13148 KB |
ok, correct split |
55 |
Correct |
3 ms |
13144 KB |
ok, correct split |
56 |
Correct |
3 ms |
13148 KB |
ok, correct split |
57 |
Correct |
3 ms |
13404 KB |
ok, correct split |
58 |
Correct |
4 ms |
13404 KB |
ok, correct split |
59 |
Correct |
4 ms |
13404 KB |
ok, correct split |
60 |
Correct |
4 ms |
13404 KB |
ok, correct split |
61 |
Correct |
4 ms |
13556 KB |
ok, correct split |
62 |
Correct |
4 ms |
13404 KB |
ok, correct split |
63 |
Correct |
4 ms |
13660 KB |
ok, correct split |
64 |
Correct |
5 ms |
13660 KB |
ok, correct split |
65 |
Correct |
4 ms |
13516 KB |
ok, correct split |
66 |
Correct |
3 ms |
13144 KB |
ok, correct split |
67 |
Correct |
4 ms |
13660 KB |
ok, correct split |
68 |
Correct |
3 ms |
13148 KB |
ok, correct split |
69 |
Correct |
3 ms |
13148 KB |
ok, correct split |
70 |
Correct |
3 ms |
13148 KB |
ok, correct split |
71 |
Correct |
4 ms |
13400 KB |
ok, correct split |
72 |
Correct |
4 ms |
13404 KB |
ok, correct split |
73 |
Correct |
4 ms |
13520 KB |
ok, correct split |
74 |
Correct |
5 ms |
13660 KB |
ok, correct split |
75 |
Correct |
5 ms |
13660 KB |
ok, correct split |
76 |
Correct |
5 ms |
13660 KB |
ok, correct split |
77 |
Correct |
5 ms |
13660 KB |
ok, correct split |
78 |
Correct |
5 ms |
13320 KB |
ok, correct split |
79 |
Correct |
4 ms |
13404 KB |
ok, correct split |
80 |
Correct |
5 ms |
13660 KB |
ok, correct split |
81 |
Correct |
4 ms |
13660 KB |
ok, correct split |
82 |
Correct |
5 ms |
13660 KB |
ok, correct split |
83 |
Correct |
4 ms |
13404 KB |
ok, correct split |
84 |
Correct |
4 ms |
13404 KB |
ok, no valid answer |
85 |
Correct |
4 ms |
13572 KB |
ok, correct split |
86 |
Correct |
4 ms |
13404 KB |
ok, correct split |
87 |
Correct |
3 ms |
13148 KB |
ok, no valid answer |
88 |
Correct |
3 ms |
13148 KB |
ok, no valid answer |
89 |
Correct |
4 ms |
13404 KB |
ok, no valid answer |
90 |
Correct |
5 ms |
13404 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
13660 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
13656 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
13660 KB |
ok, no valid answer |
94 |
Correct |
82 ms |
25488 KB |
ok, correct split |
95 |
Correct |
100 ms |
28664 KB |
ok, correct split |
96 |
Correct |
104 ms |
27424 KB |
ok, correct split |
97 |
Correct |
25 ms |
17740 KB |
ok, correct split |
98 |
Correct |
27 ms |
17936 KB |
ok, correct split |
99 |
Correct |
36 ms |
19804 KB |
ok, correct split |
100 |
Correct |
96 ms |
27764 KB |
ok, correct split |
101 |
Correct |
90 ms |
26616 KB |
ok, correct split |
102 |
Correct |
110 ms |
31304 KB |
ok, correct split |
103 |
Correct |
95 ms |
30540 KB |
ok, correct split |
104 |
Correct |
82 ms |
28620 KB |
ok, correct split |
105 |
Correct |
42 ms |
19996 KB |
ok, correct split |
106 |
Correct |
88 ms |
29008 KB |
ok, correct split |
107 |
Correct |
67 ms |
24136 KB |
ok, correct split |
108 |
Correct |
69 ms |
24136 KB |
ok, correct split |
109 |
Correct |
93 ms |
27168 KB |
ok, correct split |
110 |
Correct |
137 ms |
34424 KB |
ok, correct split |
111 |
Correct |
133 ms |
34264 KB |
ok, correct split |
112 |
Correct |
126 ms |
34892 KB |
ok, correct split |
113 |
Correct |
124 ms |
35072 KB |
ok, correct split |
114 |
Correct |
14 ms |
15704 KB |
ok, correct split |
115 |
Correct |
16 ms |
15324 KB |
ok, correct split |
116 |
Correct |
96 ms |
28236 KB |
ok, correct split |
117 |
Correct |
87 ms |
28044 KB |
ok, correct split |
118 |
Correct |
74 ms |
24396 KB |
ok, correct split |
119 |
Correct |
91 ms |
24244 KB |
ok, correct split |
120 |
Correct |
91 ms |
26524 KB |
ok, correct split |
121 |
Correct |
66 ms |
24272 KB |
ok, no valid answer |
122 |
Correct |
67 ms |
24804 KB |
ok, no valid answer |
123 |
Correct |
91 ms |
27752 KB |
ok, no valid answer |
124 |
Correct |
96 ms |
27552 KB |
ok, no valid answer |
125 |
Correct |
76 ms |
29008 KB |
ok, no valid answer |
126 |
Correct |
54 ms |
26060 KB |
ok, no valid answer |
127 |
Correct |
84 ms |
29804 KB |
ok, no valid answer |