#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//#define int ll
#define ve vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fv(a, c) for(int (a) = (1); (a) <= (c); (a)++)
#define fz(a, c) for(int (a) = (0); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define pb push_back
#define in insert
#define ss second
#define ff first
#define vi vector <int>
#define fa(a, v) for(int (a) : (v))
#define mnel(a) *min_element(all(a))
#define mxel(a) *max_element(all(a))
#define si set<int>
#define sov(a) sort(all((a)))
ve<vi> G, C;
vi num, siz, low;
int n, x;
pii X, Y, Z;
bool found = 0, sol = 0;
tuple<int, int, int> top ,bottom;
vector <bool> B;
void dfs (int u, int p){
siz[u] = 1;
x ++;
num[u] = x;
low[u] = x;
bool ok = 1;
fa(v, G[u]){
if(num[v] == 0){
dfs(v, u);
siz[u] += siz[v];
low[u] = min(low[v], low[u]);
if(siz[v] >= X.ff)
ok = 0;
C[u].pb(v);
}
else
if(v != p)
low[u] = min(low[u], num[v]);
}
if(siz[u] < X.ff)
ok = 0;
if(ok && !found){
found = 1;
int cur = siz[u];
fa(v, C[u]){
if(low[v] < num[u]){
if(cur - siz[v] >= X.ff){
B[v] = 1;
cur -= siz[v];
}
}
}
int opt = n - cur;
if(opt >= Y.ff){
sol = 1;
top = {Y.ff, Y.ss, p};
bottom = {X.ff, X.ss, u};
}
else
if(opt >= X.ff){
sol = 1;
top = {X.ff, X.ss, p};
bottom = {Y.ff, Y.ss, u};
}
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
vi ans(n);
int m = p.size();
n = nn;
G = ve<vi> (n);
C = ve<vi> (n);
num = vi (n);
siz = vi (n);
low = vi (n);
B = ve<bool> (n);
queue <int> Q;
fp(i,0,m){
G[p[i]].pb(q[i]);
G[q[i]].pb(p[i]);
}
ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
sort(all(A));
X = A[0], Y = A[1], Z = A[2];
dfs(0, -1);
if(sol){
ans = vi (n, Z.ss);
int sz, d, s;
tie(sz, d, s) = bottom;
ans[s] = d;
sz --;
Q.push(s);
while(Q.size()){
int u = Q.front();
Q.pop();
fa(v, C[u]){
if(!B[v]){
if(sz > 0){
ans[v] = d;
Q.push(v);
sz --;
}
}
}
}
tie(sz, d, s) = top;
ans[s] = d;
sz--;
Q.push(s);
while(Q.size()){
int u = Q.front();
Q.pop();
fa(v, G[u]){
if(ans[v] == Z.ss){
if(sz > 0){
sz--;
ans[v] = d;
Q.push(v);
}
}
}
}
}
else
ans = vi (n);
return ans;
}
Compilation message
split.cpp: In function 'void dfs(int, int)':
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:47:5: note: in expansion of macro 'fa'
47 | fa(v, G[u]){
| ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:66:9: note: in expansion of macro 'fa'
66 | fa(v, C[u]){
| ^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
| ^
split.cpp:103:5: note: in expansion of macro 'fp'
103 | fp(i,0,m){
| ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:122:13: note: in expansion of macro 'fa'
122 | fa(v, C[u]){
| ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:140:13: note: in expansion of macro 'fa'
140 | fa(v, G[u]){
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
ok, correct split |
2 |
Correct |
1 ms |
204 KB |
ok, correct split |
3 |
Correct |
1 ms |
204 KB |
ok, correct split |
4 |
Correct |
1 ms |
204 KB |
ok, correct split |
5 |
Correct |
1 ms |
204 KB |
ok, correct split |
6 |
Correct |
1 ms |
204 KB |
ok, correct split |
7 |
Correct |
103 ms |
23328 KB |
ok, correct split |
8 |
Correct |
91 ms |
21684 KB |
ok, correct split |
9 |
Correct |
117 ms |
20916 KB |
ok, correct split |
10 |
Correct |
105 ms |
24880 KB |
ok, correct split |
11 |
Correct |
102 ms |
24872 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
ok, correct split |
2 |
Correct |
1 ms |
204 KB |
ok, correct split |
3 |
Correct |
1 ms |
204 KB |
ok, correct split |
4 |
Correct |
105 ms |
18724 KB |
ok, correct split |
5 |
Correct |
81 ms |
12980 KB |
ok, correct split |
6 |
Correct |
95 ms |
24900 KB |
ok, correct split |
7 |
Correct |
93 ms |
21448 KB |
ok, correct split |
8 |
Correct |
119 ms |
17860 KB |
ok, correct split |
9 |
Correct |
96 ms |
15528 KB |
ok, correct split |
10 |
Correct |
58 ms |
12928 KB |
ok, correct split |
11 |
Correct |
54 ms |
12988 KB |
ok, correct split |
12 |
Correct |
56 ms |
13372 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
ok, correct split |
2 |
Correct |
94 ms |
13104 KB |
ok, correct split |
3 |
Correct |
28 ms |
5796 KB |
ok, correct split |
4 |
Correct |
1 ms |
204 KB |
ok, correct split |
5 |
Correct |
95 ms |
18684 KB |
ok, correct split |
6 |
Correct |
92 ms |
18328 KB |
ok, correct split |
7 |
Correct |
105 ms |
18116 KB |
ok, correct split |
8 |
Correct |
101 ms |
19652 KB |
ok, correct split |
9 |
Correct |
93 ms |
17956 KB |
ok, correct split |
10 |
Correct |
22 ms |
4812 KB |
ok, no valid answer |
11 |
Correct |
33 ms |
7188 KB |
ok, no valid answer |
12 |
Correct |
74 ms |
13540 KB |
ok, no valid answer |
13 |
Correct |
78 ms |
13988 KB |
ok, no valid answer |
14 |
Correct |
58 ms |
13280 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
ok, correct split |
2 |
Correct |
1 ms |
204 KB |
ok, no valid answer |
3 |
Correct |
1 ms |
204 KB |
ok, correct split |
4 |
Correct |
1 ms |
204 KB |
ok, correct split |
5 |
Correct |
1 ms |
204 KB |
ok, correct split |
6 |
Correct |
1 ms |
204 KB |
ok, correct split |
7 |
Correct |
1 ms |
204 KB |
ok, correct split |
8 |
Correct |
1 ms |
204 KB |
ok, correct split |
9 |
Correct |
3 ms |
716 KB |
ok, correct split |
10 |
Correct |
3 ms |
588 KB |
ok, correct split |
11 |
Correct |
1 ms |
204 KB |
ok, correct split |
12 |
Correct |
3 ms |
588 KB |
ok, correct split |
13 |
Correct |
1 ms |
204 KB |
ok, correct split |
14 |
Correct |
1 ms |
204 KB |
ok, correct split |
15 |
Correct |
1 ms |
204 KB |
ok, correct split |
16 |
Correct |
1 ms |
204 KB |
ok, correct split |
17 |
Correct |
1 ms |
204 KB |
ok, correct split |
18 |
Correct |
1 ms |
204 KB |
ok, correct split |
19 |
Correct |
1 ms |
332 KB |
ok, correct split |
20 |
Correct |
2 ms |
332 KB |
ok, correct split |
21 |
Correct |
3 ms |
716 KB |
ok, correct split |
22 |
Correct |
2 ms |
588 KB |
ok, correct split |
23 |
Correct |
2 ms |
716 KB |
ok, correct split |
24 |
Correct |
2 ms |
716 KB |
ok, correct split |
25 |
Correct |
2 ms |
716 KB |
ok, correct split |
26 |
Correct |
3 ms |
588 KB |
ok, correct split |
27 |
Correct |
3 ms |
588 KB |
ok, correct split |
28 |
Correct |
3 ms |
588 KB |
ok, correct split |
29 |
Correct |
1 ms |
204 KB |
ok, correct split |
30 |
Correct |
3 ms |
588 KB |
ok, correct split |
31 |
Correct |
1 ms |
332 KB |
ok, correct split |
32 |
Correct |
1 ms |
204 KB |
ok, correct split |
33 |
Correct |
1 ms |
332 KB |
ok, correct split |
34 |
Correct |
2 ms |
588 KB |
ok, correct split |
35 |
Correct |
3 ms |
588 KB |
ok, correct split |
36 |
Correct |
2 ms |
588 KB |
ok, correct split |
37 |
Correct |
3 ms |
588 KB |
ok, correct split |
38 |
Correct |
3 ms |
716 KB |
ok, correct split |
39 |
Correct |
3 ms |
588 KB |
ok, correct split |
40 |
Correct |
3 ms |
588 KB |
ok, correct split |
41 |
Correct |
2 ms |
460 KB |
ok, correct split |
42 |
Correct |
2 ms |
460 KB |
ok, correct split |
43 |
Correct |
3 ms |
588 KB |
ok, correct split |
44 |
Correct |
3 ms |
588 KB |
ok, correct split |
45 |
Correct |
3 ms |
588 KB |
ok, correct split |
46 |
Correct |
2 ms |
716 KB |
ok, correct split |
47 |
Correct |
2 ms |
716 KB |
ok, no valid answer |
48 |
Correct |
2 ms |
588 KB |
ok, correct split |
49 |
Correct |
2 ms |
716 KB |
ok, correct split |
50 |
Correct |
1 ms |
204 KB |
ok, no valid answer |
51 |
Correct |
1 ms |
204 KB |
ok, no valid answer |
52 |
Correct |
2 ms |
588 KB |
ok, no valid answer |
53 |
Correct |
3 ms |
588 KB |
ok, no valid answer |
54 |
Correct |
2 ms |
588 KB |
ok, no valid answer |
55 |
Correct |
3 ms |
588 KB |
ok, no valid answer |
56 |
Correct |
2 ms |
588 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
ok, correct split |
2 |
Correct |
1 ms |
204 KB |
ok, correct split |
3 |
Correct |
1 ms |
204 KB |
ok, correct split |
4 |
Correct |
1 ms |
204 KB |
ok, correct split |
5 |
Correct |
1 ms |
204 KB |
ok, correct split |
6 |
Correct |
1 ms |
204 KB |
ok, correct split |
7 |
Correct |
103 ms |
23328 KB |
ok, correct split |
8 |
Correct |
91 ms |
21684 KB |
ok, correct split |
9 |
Correct |
117 ms |
20916 KB |
ok, correct split |
10 |
Correct |
105 ms |
24880 KB |
ok, correct split |
11 |
Correct |
102 ms |
24872 KB |
ok, correct split |
12 |
Correct |
1 ms |
204 KB |
ok, correct split |
13 |
Correct |
1 ms |
204 KB |
ok, correct split |
14 |
Correct |
1 ms |
204 KB |
ok, correct split |
15 |
Correct |
105 ms |
18724 KB |
ok, correct split |
16 |
Correct |
81 ms |
12980 KB |
ok, correct split |
17 |
Correct |
95 ms |
24900 KB |
ok, correct split |
18 |
Correct |
93 ms |
21448 KB |
ok, correct split |
19 |
Correct |
119 ms |
17860 KB |
ok, correct split |
20 |
Correct |
96 ms |
15528 KB |
ok, correct split |
21 |
Correct |
58 ms |
12928 KB |
ok, correct split |
22 |
Correct |
54 ms |
12988 KB |
ok, correct split |
23 |
Correct |
56 ms |
13372 KB |
ok, correct split |
24 |
Correct |
1 ms |
204 KB |
ok, correct split |
25 |
Correct |
94 ms |
13104 KB |
ok, correct split |
26 |
Correct |
28 ms |
5796 KB |
ok, correct split |
27 |
Correct |
1 ms |
204 KB |
ok, correct split |
28 |
Correct |
95 ms |
18684 KB |
ok, correct split |
29 |
Correct |
92 ms |
18328 KB |
ok, correct split |
30 |
Correct |
105 ms |
18116 KB |
ok, correct split |
31 |
Correct |
101 ms |
19652 KB |
ok, correct split |
32 |
Correct |
93 ms |
17956 KB |
ok, correct split |
33 |
Correct |
22 ms |
4812 KB |
ok, no valid answer |
34 |
Correct |
33 ms |
7188 KB |
ok, no valid answer |
35 |
Correct |
74 ms |
13540 KB |
ok, no valid answer |
36 |
Correct |
78 ms |
13988 KB |
ok, no valid answer |
37 |
Correct |
58 ms |
13280 KB |
ok, no valid answer |
38 |
Correct |
1 ms |
204 KB |
ok, correct split |
39 |
Correct |
1 ms |
204 KB |
ok, no valid answer |
40 |
Correct |
1 ms |
204 KB |
ok, correct split |
41 |
Correct |
1 ms |
204 KB |
ok, correct split |
42 |
Correct |
1 ms |
204 KB |
ok, correct split |
43 |
Correct |
1 ms |
204 KB |
ok, correct split |
44 |
Correct |
1 ms |
204 KB |
ok, correct split |
45 |
Correct |
1 ms |
204 KB |
ok, correct split |
46 |
Correct |
3 ms |
716 KB |
ok, correct split |
47 |
Correct |
3 ms |
588 KB |
ok, correct split |
48 |
Correct |
1 ms |
204 KB |
ok, correct split |
49 |
Correct |
3 ms |
588 KB |
ok, correct split |
50 |
Correct |
1 ms |
204 KB |
ok, correct split |
51 |
Correct |
1 ms |
204 KB |
ok, correct split |
52 |
Correct |
1 ms |
204 KB |
ok, correct split |
53 |
Correct |
1 ms |
204 KB |
ok, correct split |
54 |
Correct |
1 ms |
204 KB |
ok, correct split |
55 |
Correct |
1 ms |
204 KB |
ok, correct split |
56 |
Correct |
1 ms |
332 KB |
ok, correct split |
57 |
Correct |
2 ms |
332 KB |
ok, correct split |
58 |
Correct |
3 ms |
716 KB |
ok, correct split |
59 |
Correct |
2 ms |
588 KB |
ok, correct split |
60 |
Correct |
2 ms |
716 KB |
ok, correct split |
61 |
Correct |
2 ms |
716 KB |
ok, correct split |
62 |
Correct |
2 ms |
716 KB |
ok, correct split |
63 |
Correct |
3 ms |
588 KB |
ok, correct split |
64 |
Correct |
3 ms |
588 KB |
ok, correct split |
65 |
Correct |
3 ms |
588 KB |
ok, correct split |
66 |
Correct |
1 ms |
204 KB |
ok, correct split |
67 |
Correct |
3 ms |
588 KB |
ok, correct split |
68 |
Correct |
1 ms |
332 KB |
ok, correct split |
69 |
Correct |
1 ms |
204 KB |
ok, correct split |
70 |
Correct |
1 ms |
332 KB |
ok, correct split |
71 |
Correct |
2 ms |
588 KB |
ok, correct split |
72 |
Correct |
3 ms |
588 KB |
ok, correct split |
73 |
Correct |
2 ms |
588 KB |
ok, correct split |
74 |
Correct |
3 ms |
588 KB |
ok, correct split |
75 |
Correct |
3 ms |
716 KB |
ok, correct split |
76 |
Correct |
3 ms |
588 KB |
ok, correct split |
77 |
Correct |
3 ms |
588 KB |
ok, correct split |
78 |
Correct |
2 ms |
460 KB |
ok, correct split |
79 |
Correct |
2 ms |
460 KB |
ok, correct split |
80 |
Correct |
3 ms |
588 KB |
ok, correct split |
81 |
Correct |
3 ms |
588 KB |
ok, correct split |
82 |
Correct |
3 ms |
588 KB |
ok, correct split |
83 |
Correct |
2 ms |
716 KB |
ok, correct split |
84 |
Correct |
2 ms |
716 KB |
ok, no valid answer |
85 |
Correct |
2 ms |
588 KB |
ok, correct split |
86 |
Correct |
2 ms |
716 KB |
ok, correct split |
87 |
Correct |
1 ms |
204 KB |
ok, no valid answer |
88 |
Correct |
1 ms |
204 KB |
ok, no valid answer |
89 |
Correct |
2 ms |
588 KB |
ok, no valid answer |
90 |
Correct |
3 ms |
588 KB |
ok, no valid answer |
91 |
Correct |
2 ms |
588 KB |
ok, no valid answer |
92 |
Correct |
3 ms |
588 KB |
ok, no valid answer |
93 |
Correct |
2 ms |
588 KB |
ok, no valid answer |
94 |
Correct |
102 ms |
17796 KB |
ok, correct split |
95 |
Correct |
139 ms |
23836 KB |
ok, correct split |
96 |
Correct |
118 ms |
21960 KB |
ok, correct split |
97 |
Correct |
30 ms |
5948 KB |
ok, correct split |
98 |
Correct |
32 ms |
6000 KB |
ok, correct split |
99 |
Correct |
46 ms |
8356 KB |
ok, correct split |
100 |
Correct |
153 ms |
18500 KB |
ok, correct split |
101 |
Correct |
117 ms |
17360 KB |
ok, correct split |
102 |
Correct |
103 ms |
16696 KB |
ok, correct split |
103 |
Correct |
93 ms |
16380 KB |
ok, correct split |
104 |
Correct |
93 ms |
16560 KB |
ok, correct split |
105 |
Correct |
67 ms |
8876 KB |
ok, correct split |
106 |
Correct |
101 ms |
16300 KB |
ok, correct split |
107 |
Correct |
80 ms |
14128 KB |
ok, correct split |
108 |
Correct |
80 ms |
14152 KB |
ok, correct split |
109 |
Correct |
149 ms |
17896 KB |
ok, correct split |
110 |
Correct |
125 ms |
18748 KB |
ok, correct split |
111 |
Correct |
126 ms |
18856 KB |
ok, correct split |
112 |
Correct |
121 ms |
17448 KB |
ok, correct split |
113 |
Correct |
123 ms |
17456 KB |
ok, correct split |
114 |
Correct |
12 ms |
2428 KB |
ok, correct split |
115 |
Correct |
12 ms |
2124 KB |
ok, correct split |
116 |
Correct |
162 ms |
18600 KB |
ok, correct split |
117 |
Correct |
125 ms |
18632 KB |
ok, correct split |
118 |
Correct |
100 ms |
15580 KB |
ok, correct split |
119 |
Correct |
116 ms |
15556 KB |
ok, correct split |
120 |
Correct |
118 ms |
20520 KB |
ok, correct split |
121 |
Correct |
87 ms |
14128 KB |
ok, no valid answer |
122 |
Correct |
79 ms |
14020 KB |
ok, no valid answer |
123 |
Correct |
138 ms |
18748 KB |
ok, no valid answer |
124 |
Correct |
130 ms |
18492 KB |
ok, no valid answer |
125 |
Correct |
82 ms |
14920 KB |
ok, no valid answer |
126 |
Correct |
53 ms |
11928 KB |
ok, no valid answer |
127 |
Correct |
111 ms |
16028 KB |
ok, no valid answer |