#include "split.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
const int MAXN = 100055;
const int MAXM = 200055;
vector<int> G[MAXN], T[MAXN];
vector<vector<int>> PathV;
int cnt[MAXN], col[MAXN], colcnt[MAXN];
int A[MAXM], B[MAXM];
bitset<MAXN> chk, colchk;
int ud[MAXN];
int Ans[MAXN];
int N, M, CA, CB, CC, CO[4], Rt, K;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
void normdfs(int i, int &c, int key) {
if(!c) return;
chk[i] = false; c--; Ans[i] = key;
for(int v : G[i]) if(chk[v]) normdfs(v, c, key);
}
bool normAns() {
for(int i = 0; i < N; i++) G[i].clear();
for(int i = 0; i < M; i++) fg(G, A[i], B[i]);
chk.reset();
for(int i = 0; i < N; i++)
if(Ans[i] < 1 || 2 < Ans[i]) Ans[i] = 3;
int x = -1;
for(int i = 0; i < N; i++) if(1 == Ans[i]) { x = i; chk[i] = true; }
if(chk.count() < CA) return false;
{ int c = CA; normdfs(x, c, -1); }
for(int i = 0; i < N; i++) {
if(1 == Ans[i]) Ans[i] = 3;
else if(-1 == Ans[i]) Ans[i] = 1;
}
chk.reset();
for(int i = 0; i < N; i++) if(2 == Ans[i]) chk[i] = true;
if(chk.count() < CB) return false;
{ int c = CB; normdfs(Rt, c, -2); }
for(int i = 0; i < N; i++) {
if(2 == Ans[i]) Ans[i] = 3;
else if(-2 == Ans[i]) Ans[i] = 2;
}
return true;
}
void predfs(int i) {
cnt[i] = 1;
for(int v : G[i]) if(!cnt[v]) {
predfs(v);
cnt[i] += cnt[v];
}
}
void cent(int &rt) {
const int N = cnt[rt];
for(int hi, hc;;) {
hi = hc = -1;
for(int v : G[rt]) if(cnt[v] < cnt[rt] && hc < cnt[v]) {
hi = v; hc = cnt[v];
}
if(hc*2 <= N) break;
cnt[rt] = N - hc;
cnt[hi] = N;
rt = hi;
}
}
void treedfs(int i) {
Ans[i] = 1;
for(int v : G[i]) if(cnt[v] < cnt[i])
treedfs(v);
}
bool solveTree() {
for(int v : G[Rt]) if(CA <= cnt[v]) {
fill(Ans, Ans+N, 2);
treedfs(v);
return true;
}
return false;
}
void precoldfs(int i) {
for(int v : G[i]) if(cnt[v] < cnt[i]) {
col[v] = col[i];
precoldfs(v);
}
}
void initNew() {
for(int v : G[Rt]) {
col[v] = K++;
precoldfs(v);
colcnt[col[v]] = cnt[v];
}
for(int i = 0, a, b; i < M; i++) if(A[i] != Rt && B[i] != Rt) {
a = col[A[i]];
b = col[B[i]];
if(a == b) continue;
fg(T, a, b);
}
}
void pathdfs(vector<int> &V, int i) {
colchk[i] = true; V.eb(i);
for(int v : T[i]) if(!colchk[v])
pathdfs(V, v);
}
void getPath() {
for(int i = 0; i < K; i++) if(!colchk[i]) {
PathV.eb();
pathdfs(PathV.back(), i);
}
}
bool solve() {
iota(CO, CO+4, 0);
if(CA > CB) { swap(CA, CB); swap(CO[1], CO[2]); }
if(CA > CC) { swap(CA, CC); swap(CO[1], CO[3]); }
if(CB > CC) { swap(CB, CC); swap(CO[2], CO[3]); }
iota(ud, ud+MAXN, 0);
for(int i = 0, a, b; i < M; i++) {
a = A[i]; b = B[i];
if(uf(a) == uf(b)) continue;
uf(a, b);
fg(G, a, b);
}
predfs(0); cent(Rt);
if(solveTree()) return true;
initNew();
getPath();
for(; !PathV.empty();) {
int sum = 0;
for(int v : PathV.back()) sum += colcnt[v];
if(sum < CA) PathV.pop_back();
else break;
}
if(PathV.empty()) return false;
vector<int> PV;
{
int sum = 0;
for(int v : PathV.back()) {
sum += colcnt[v];
PV.eb(v);
if(sum >= CA) break;
}
}
fill(Ans, Ans+N, 2);
colchk.reset();
for(int v : PV) colchk[v] = true;
for(int i = 0; i < N; i++) if(i != Rt && colchk[col[i]]) Ans[i] = 1;
return true;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
::N = n; ::M = sz(p);
::CA = a; ::CB = b; ::CC = c;
for(int i = 0; i < ::M; i++) {
::A[i] = p[i];
::B[i] = q[i];
}
if(!solve() || !normAns()) return vector<int>(::N, 0);
vector<int> res;
for(int i = 0; i < ::N; i++) {
if(1 == ::Ans[i]) res.eb(::CO[1]);
else if(2 == ::Ans[i]) res.eb(::CO[2]);
else res.eb(::CO[3]);
}
return res;
}
Compilation message
split.cpp: In function 'bool normAns()':
split.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(chk.count() < CA) return false;
~~~~~~~~~~~~^~~~
split.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(chk.count() < CB) return false;
~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5496 KB |
ok, correct split |
2 |
Correct |
7 ms |
5496 KB |
ok, correct split |
3 |
Correct |
7 ms |
5496 KB |
ok, correct split |
4 |
Correct |
6 ms |
5368 KB |
ok, correct split |
5 |
Correct |
6 ms |
5496 KB |
ok, correct split |
6 |
Correct |
6 ms |
5496 KB |
ok, correct split |
7 |
Correct |
147 ms |
16868 KB |
ok, correct split |
8 |
Correct |
104 ms |
15480 KB |
ok, correct split |
9 |
Correct |
124 ms |
15332 KB |
ok, correct split |
10 |
Correct |
125 ms |
17016 KB |
ok, correct split |
11 |
Correct |
134 ms |
16476 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5368 KB |
ok, correct split |
2 |
Correct |
6 ms |
5368 KB |
ok, correct split |
3 |
Correct |
6 ms |
5368 KB |
ok, correct split |
4 |
Correct |
137 ms |
14384 KB |
ok, correct split |
5 |
Correct |
101 ms |
12536 KB |
ok, correct split |
6 |
Correct |
120 ms |
17140 KB |
ok, correct split |
7 |
Correct |
132 ms |
15484 KB |
ok, correct split |
8 |
Correct |
171 ms |
15756 KB |
ok, correct split |
9 |
Correct |
106 ms |
12408 KB |
ok, correct split |
10 |
Correct |
75 ms |
12912 KB |
ok, correct split |
11 |
Correct |
77 ms |
12888 KB |
ok, correct split |
12 |
Correct |
80 ms |
12892 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5496 KB |
ok, correct split |
2 |
Correct |
105 ms |
12548 KB |
ok, correct split |
3 |
Correct |
39 ms |
8440 KB |
ok, correct split |
4 |
Correct |
6 ms |
5496 KB |
ok, correct split |
5 |
Correct |
110 ms |
13944 KB |
ok, correct split |
6 |
Correct |
107 ms |
13804 KB |
ok, correct split |
7 |
Correct |
122 ms |
13688 KB |
ok, correct split |
8 |
Correct |
107 ms |
14456 KB |
ok, correct split |
9 |
Correct |
112 ms |
13540 KB |
ok, correct split |
10 |
Correct |
32 ms |
7772 KB |
ok, no valid answer |
11 |
Correct |
47 ms |
9048 KB |
ok, no valid answer |
12 |
Correct |
94 ms |
15504 KB |
ok, no valid answer |
13 |
Correct |
99 ms |
12856 KB |
ok, no valid answer |
14 |
Correct |
87 ms |
18020 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5368 KB |
ok, correct split |
2 |
Correct |
6 ms |
5368 KB |
ok, no valid answer |
3 |
Correct |
6 ms |
5496 KB |
ok, correct split |
4 |
Correct |
6 ms |
5496 KB |
ok, correct split |
5 |
Correct |
6 ms |
5496 KB |
ok, correct split |
6 |
Correct |
6 ms |
5496 KB |
ok, correct split |
7 |
Correct |
6 ms |
5368 KB |
ok, correct split |
8 |
Correct |
7 ms |
5496 KB |
ok, correct split |
9 |
Correct |
9 ms |
5624 KB |
ok, correct split |
10 |
Correct |
8 ms |
5752 KB |
ok, correct split |
11 |
Correct |
7 ms |
5496 KB |
ok, correct split |
12 |
Correct |
9 ms |
5752 KB |
ok, correct split |
13 |
Correct |
6 ms |
5368 KB |
ok, correct split |
14 |
Correct |
6 ms |
5496 KB |
ok, correct split |
15 |
Correct |
6 ms |
5496 KB |
ok, correct split |
16 |
Correct |
6 ms |
5368 KB |
ok, correct split |
17 |
Correct |
6 ms |
5496 KB |
ok, correct split |
18 |
Correct |
6 ms |
5368 KB |
ok, correct split |
19 |
Correct |
7 ms |
5496 KB |
ok, correct split |
20 |
Correct |
7 ms |
5496 KB |
ok, correct split |
21 |
Correct |
8 ms |
5648 KB |
ok, correct split |
22 |
Correct |
8 ms |
5624 KB |
ok, correct split |
23 |
Correct |
8 ms |
5752 KB |
ok, correct split |
24 |
Correct |
8 ms |
5752 KB |
ok, correct split |
25 |
Correct |
8 ms |
5624 KB |
ok, correct split |
26 |
Correct |
9 ms |
5752 KB |
ok, correct split |
27 |
Correct |
9 ms |
5756 KB |
ok, correct split |
28 |
Correct |
9 ms |
5624 KB |
ok, correct split |
29 |
Correct |
7 ms |
5496 KB |
ok, correct split |
30 |
Correct |
9 ms |
5752 KB |
ok, correct split |
31 |
Correct |
7 ms |
5496 KB |
ok, correct split |
32 |
Correct |
7 ms |
5496 KB |
ok, correct split |
33 |
Correct |
7 ms |
5496 KB |
ok, correct split |
34 |
Correct |
8 ms |
5628 KB |
ok, correct split |
35 |
Correct |
10 ms |
5624 KB |
ok, correct split |
36 |
Correct |
8 ms |
5624 KB |
ok, correct split |
37 |
Correct |
11 ms |
5752 KB |
ok, correct split |
38 |
Correct |
10 ms |
5880 KB |
ok, correct split |
39 |
Correct |
9 ms |
5752 KB |
ok, correct split |
40 |
Correct |
10 ms |
5876 KB |
ok, correct split |
41 |
Correct |
10 ms |
5624 KB |
ok, correct split |
42 |
Correct |
8 ms |
5624 KB |
ok, correct split |
43 |
Correct |
9 ms |
5752 KB |
ok, correct split |
44 |
Correct |
9 ms |
5752 KB |
ok, correct split |
45 |
Correct |
9 ms |
5752 KB |
ok, correct split |
46 |
Correct |
8 ms |
5752 KB |
ok, correct split |
47 |
Correct |
8 ms |
5752 KB |
ok, no valid answer |
48 |
Correct |
8 ms |
5752 KB |
ok, correct split |
49 |
Correct |
8 ms |
5752 KB |
ok, correct split |
50 |
Correct |
7 ms |
5496 KB |
ok, no valid answer |
51 |
Correct |
6 ms |
5368 KB |
ok, no valid answer |
52 |
Correct |
8 ms |
5624 KB |
ok, no valid answer |
53 |
Correct |
9 ms |
5752 KB |
ok, no valid answer |
54 |
Correct |
8 ms |
5880 KB |
ok, no valid answer |
55 |
Correct |
8 ms |
5752 KB |
ok, no valid answer |
56 |
Correct |
9 ms |
5880 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5496 KB |
ok, correct split |
2 |
Correct |
7 ms |
5496 KB |
ok, correct split |
3 |
Correct |
7 ms |
5496 KB |
ok, correct split |
4 |
Correct |
6 ms |
5368 KB |
ok, correct split |
5 |
Correct |
6 ms |
5496 KB |
ok, correct split |
6 |
Correct |
6 ms |
5496 KB |
ok, correct split |
7 |
Correct |
147 ms |
16868 KB |
ok, correct split |
8 |
Correct |
104 ms |
15480 KB |
ok, correct split |
9 |
Correct |
124 ms |
15332 KB |
ok, correct split |
10 |
Correct |
125 ms |
17016 KB |
ok, correct split |
11 |
Correct |
134 ms |
16476 KB |
ok, correct split |
12 |
Correct |
6 ms |
5368 KB |
ok, correct split |
13 |
Correct |
6 ms |
5368 KB |
ok, correct split |
14 |
Correct |
6 ms |
5368 KB |
ok, correct split |
15 |
Correct |
137 ms |
14384 KB |
ok, correct split |
16 |
Correct |
101 ms |
12536 KB |
ok, correct split |
17 |
Correct |
120 ms |
17140 KB |
ok, correct split |
18 |
Correct |
132 ms |
15484 KB |
ok, correct split |
19 |
Correct |
171 ms |
15756 KB |
ok, correct split |
20 |
Correct |
106 ms |
12408 KB |
ok, correct split |
21 |
Correct |
75 ms |
12912 KB |
ok, correct split |
22 |
Correct |
77 ms |
12888 KB |
ok, correct split |
23 |
Correct |
80 ms |
12892 KB |
ok, correct split |
24 |
Correct |
6 ms |
5496 KB |
ok, correct split |
25 |
Correct |
105 ms |
12548 KB |
ok, correct split |
26 |
Correct |
39 ms |
8440 KB |
ok, correct split |
27 |
Correct |
6 ms |
5496 KB |
ok, correct split |
28 |
Correct |
110 ms |
13944 KB |
ok, correct split |
29 |
Correct |
107 ms |
13804 KB |
ok, correct split |
30 |
Correct |
122 ms |
13688 KB |
ok, correct split |
31 |
Correct |
107 ms |
14456 KB |
ok, correct split |
32 |
Correct |
112 ms |
13540 KB |
ok, correct split |
33 |
Correct |
32 ms |
7772 KB |
ok, no valid answer |
34 |
Correct |
47 ms |
9048 KB |
ok, no valid answer |
35 |
Correct |
94 ms |
15504 KB |
ok, no valid answer |
36 |
Correct |
99 ms |
12856 KB |
ok, no valid answer |
37 |
Correct |
87 ms |
18020 KB |
ok, no valid answer |
38 |
Correct |
6 ms |
5368 KB |
ok, correct split |
39 |
Correct |
6 ms |
5368 KB |
ok, no valid answer |
40 |
Correct |
6 ms |
5496 KB |
ok, correct split |
41 |
Correct |
6 ms |
5496 KB |
ok, correct split |
42 |
Correct |
6 ms |
5496 KB |
ok, correct split |
43 |
Correct |
6 ms |
5496 KB |
ok, correct split |
44 |
Correct |
6 ms |
5368 KB |
ok, correct split |
45 |
Correct |
7 ms |
5496 KB |
ok, correct split |
46 |
Correct |
9 ms |
5624 KB |
ok, correct split |
47 |
Correct |
8 ms |
5752 KB |
ok, correct split |
48 |
Correct |
7 ms |
5496 KB |
ok, correct split |
49 |
Correct |
9 ms |
5752 KB |
ok, correct split |
50 |
Correct |
6 ms |
5368 KB |
ok, correct split |
51 |
Correct |
6 ms |
5496 KB |
ok, correct split |
52 |
Correct |
6 ms |
5496 KB |
ok, correct split |
53 |
Correct |
6 ms |
5368 KB |
ok, correct split |
54 |
Correct |
6 ms |
5496 KB |
ok, correct split |
55 |
Correct |
6 ms |
5368 KB |
ok, correct split |
56 |
Correct |
7 ms |
5496 KB |
ok, correct split |
57 |
Correct |
7 ms |
5496 KB |
ok, correct split |
58 |
Correct |
8 ms |
5648 KB |
ok, correct split |
59 |
Correct |
8 ms |
5624 KB |
ok, correct split |
60 |
Correct |
8 ms |
5752 KB |
ok, correct split |
61 |
Correct |
8 ms |
5752 KB |
ok, correct split |
62 |
Correct |
8 ms |
5624 KB |
ok, correct split |
63 |
Correct |
9 ms |
5752 KB |
ok, correct split |
64 |
Correct |
9 ms |
5756 KB |
ok, correct split |
65 |
Correct |
9 ms |
5624 KB |
ok, correct split |
66 |
Correct |
7 ms |
5496 KB |
ok, correct split |
67 |
Correct |
9 ms |
5752 KB |
ok, correct split |
68 |
Correct |
7 ms |
5496 KB |
ok, correct split |
69 |
Correct |
7 ms |
5496 KB |
ok, correct split |
70 |
Correct |
7 ms |
5496 KB |
ok, correct split |
71 |
Correct |
8 ms |
5628 KB |
ok, correct split |
72 |
Correct |
10 ms |
5624 KB |
ok, correct split |
73 |
Correct |
8 ms |
5624 KB |
ok, correct split |
74 |
Correct |
11 ms |
5752 KB |
ok, correct split |
75 |
Correct |
10 ms |
5880 KB |
ok, correct split |
76 |
Correct |
9 ms |
5752 KB |
ok, correct split |
77 |
Correct |
10 ms |
5876 KB |
ok, correct split |
78 |
Correct |
10 ms |
5624 KB |
ok, correct split |
79 |
Correct |
8 ms |
5624 KB |
ok, correct split |
80 |
Correct |
9 ms |
5752 KB |
ok, correct split |
81 |
Correct |
9 ms |
5752 KB |
ok, correct split |
82 |
Correct |
9 ms |
5752 KB |
ok, correct split |
83 |
Correct |
8 ms |
5752 KB |
ok, correct split |
84 |
Correct |
8 ms |
5752 KB |
ok, no valid answer |
85 |
Correct |
8 ms |
5752 KB |
ok, correct split |
86 |
Correct |
8 ms |
5752 KB |
ok, correct split |
87 |
Correct |
7 ms |
5496 KB |
ok, no valid answer |
88 |
Correct |
6 ms |
5368 KB |
ok, no valid answer |
89 |
Correct |
8 ms |
5624 KB |
ok, no valid answer |
90 |
Correct |
9 ms |
5752 KB |
ok, no valid answer |
91 |
Correct |
8 ms |
5880 KB |
ok, no valid answer |
92 |
Correct |
8 ms |
5752 KB |
ok, no valid answer |
93 |
Correct |
9 ms |
5880 KB |
ok, no valid answer |
94 |
Correct |
137 ms |
14996 KB |
ok, correct split |
95 |
Correct |
198 ms |
19724 KB |
ok, correct split |
96 |
Correct |
194 ms |
19064 KB |
ok, correct split |
97 |
Correct |
40 ms |
8824 KB |
ok, correct split |
98 |
Correct |
42 ms |
9080 KB |
ok, correct split |
99 |
Correct |
67 ms |
11640 KB |
ok, correct split |
100 |
Correct |
158 ms |
18424 KB |
ok, correct split |
101 |
Correct |
142 ms |
17012 KB |
ok, correct split |
102 |
Correct |
155 ms |
20008 KB |
ok, correct split |
103 |
Correct |
189 ms |
19748 KB |
ok, correct split |
104 |
Correct |
146 ms |
17996 KB |
ok, correct split |
105 |
Correct |
68 ms |
10616 KB |
ok, correct split |
106 |
Correct |
147 ms |
17868 KB |
ok, correct split |
107 |
Correct |
120 ms |
13756 KB |
ok, correct split |
108 |
Correct |
104 ms |
13560 KB |
ok, correct split |
109 |
Correct |
174 ms |
17908 KB |
ok, correct split |
110 |
Correct |
177 ms |
19824 KB |
ok, correct split |
111 |
Correct |
180 ms |
19952 KB |
ok, correct split |
112 |
Correct |
186 ms |
20464 KB |
ok, correct split |
113 |
Correct |
188 ms |
20524 KB |
ok, correct split |
114 |
Correct |
22 ms |
7160 KB |
ok, correct split |
115 |
Correct |
21 ms |
7032 KB |
ok, correct split |
116 |
Correct |
150 ms |
17508 KB |
ok, correct split |
117 |
Correct |
152 ms |
17488 KB |
ok, correct split |
118 |
Correct |
104 ms |
13560 KB |
ok, correct split |
119 |
Correct |
124 ms |
14072 KB |
ok, correct split |
120 |
Correct |
125 ms |
15840 KB |
ok, correct split |
121 |
Correct |
94 ms |
13432 KB |
ok, no valid answer |
122 |
Correct |
92 ms |
14416 KB |
ok, no valid answer |
123 |
Correct |
136 ms |
16884 KB |
ok, no valid answer |
124 |
Correct |
138 ms |
17016 KB |
ok, no valid answer |
125 |
Correct |
107 ms |
20328 KB |
ok, no valid answer |
126 |
Correct |
79 ms |
18152 KB |
ok, no valid answer |
127 |
Correct |
121 ms |
18920 KB |
ok, no valid answer |