// Fight the good fight of the faith. Take hold of the
// eternal life to which you were called when you made
// your good confession in the presence of many witnesses
// 1 Timonthy 6:12
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#define INF 1000000005ll
#define LINF 1000000000000000005ll
#define MAXN 100005
int n;
vii tadj[MAXN], adj[MAXN];
vi deg[MAXN];
bool on[MAXN];
set<int> useful;
bool vis[MAXN];
struct ST {
vi cnt;
vll sm;
vi lc, rc;
ST() {
cnt.pb(0);
sm.pb(0);
lc.pb(-1);
rc.pb(-1);
}
void add(ll p, int x, int u = 0, ll lo = 0, ll hi = INF) {
if (lo == hi) {
cnt[u] += x;
sm[u] += x * p;
return;
}
ll mid = lo + hi >> 1;
if (p <= mid) {
if (lc[u] == -1) {
lc[u] = cnt.size();
cnt.pb(0);
sm.pb(0);
lc.pb(-1);
rc.pb(-1);
}
add(p, x, lc[u], lo, mid);
} else {
if (rc[u] == -1) {
rc[u] = cnt.size();
cnt.pb(0);
sm.pb(0);
lc.pb(-1);
rc.pb(-1);
}
add(p, x, rc[u], mid + 1, hi);
}
cnt[u] = (lc[u] == -1 ? 0 : cnt[lc[u]]) + (rc[u] == -1 ? 0 : cnt[rc[u]]);
sm[u] = (lc[u] == -1 ? 0 : sm[lc[u]]) + (rc[u] == -1 ? 0 : sm[rc[u]]);
}
ll qry(int k, int u = 0, ll lo = 0, ll hi = INF) {
if (lo == hi) {
return lo * k;
}
assert(u != -1);
if (cnt[u] == k) {
return sm[u];
}
ll mid = lo + hi >> 1;
if (lc[u] == -1) {
return qry(k, rc[u], mid + 1, hi);
}
if (cnt[lc[u]] >= k) {
return qry(k, lc[u], lo, mid);
} else {
return qry(k - cnt[lc[u]], rc[u], mid + 1, hi) + sm[lc[u]];
}
}
} st[MAXN];
int k;
// first is never close parent, second is close parent
pll dp(int u, int p) {
vll vec;
ll cur = 0;
int sze = st[u].cnt[0];
assert(sze + adj[u].size() == tadj[u].size());
for (auto [v, w] : adj[u]) {
if (v == p) continue;
vis[v] = 1;
auto [a, b] = dp(v, u);
b += w;
if (b - a < 0) {
cur += b;
} else {
debug(" +%lld\n", b - a);
vec.pb(b - a);
cur += a;
sze++;
}
}
debug(" %d %d %lld\n", u, sze, cur);
for (ll i : vec) {
st[u].add(i, 1);
}
auto solve = [&] (int k) {
if (sze <= k) {
return cur;
}
int x = sze - k;
debug(" %d %d\n", x, st[u].cnt[0]);
return cur + st[u].qry(x);
};
ll ra = solve(k - 1), rb = solve(k);
for (ll i : vec) {
st[u].add(i, -1);
}
return MP(ra, rb);
}
vll minimum_closure_costs(int n, vi u, vi v, vi w) {
::n = n;
ll sm = 0;
REP (i, 0, n - 1) {
tadj[u[i]].pb(MP(v[i], w[i]));
tadj[v[i]].pb(MP(u[i], w[i]));
sm += w[i];
}
REP (i, 0, n) {
deg[tadj[i].size()].pb(i);
}
vll ans(n, 0);
RREP (k, n - 1, 1) {
::k = k;
debug("%d\n", k);
for (int i : deg[k + 1]) {
useful.insert(i);
on[i] = 1;
for (auto [u, w] : tadj[i]) {
if (on[u]) {
adj[u].pb(MP(i, w));
adj[i].pb(MP(u, w));
st[u].add(w, -1);
} else {
if (i == 23) {
debug("+%d %02d %d\n", i, u, w);
}
st[i].add(w, 1);
}
}
}
for (int i : useful) {
if (vis[i]) continue;
vis[i] = 1;
auto [a, b] = dp(i, -1);
ans[k] += b;
}
for (int i : useful) {
vis[i] = 0;
}
}
ans[0] = sm;
return ans;
}
Compilation message
roads.cpp: In member function 'void ST::add(ll, int, int, ll, ll)':
roads.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | ll mid = lo + hi >> 1;
| ~~~^~~~
roads.cpp: In member function 'll ST::qry(int, int, ll, ll)':
roads.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | ll mid = lo + hi >> 1;
| ~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
29260 KB |
Output is correct |
2 |
Correct |
33 ms |
30512 KB |
Output is correct |
3 |
Correct |
32 ms |
30604 KB |
Output is correct |
4 |
Correct |
32 ms |
29456 KB |
Output is correct |
5 |
Correct |
31 ms |
29376 KB |
Output is correct |
6 |
Correct |
31 ms |
29468 KB |
Output is correct |
7 |
Correct |
25 ms |
29268 KB |
Output is correct |
8 |
Correct |
31 ms |
29384 KB |
Output is correct |
9 |
Correct |
32 ms |
29388 KB |
Output is correct |
10 |
Correct |
26 ms |
29240 KB |
Output is correct |
11 |
Correct |
25 ms |
29204 KB |
Output is correct |
12 |
Correct |
84 ms |
34564 KB |
Output is correct |
13 |
Correct |
121 ms |
38104 KB |
Output is correct |
14 |
Correct |
187 ms |
72100 KB |
Output is correct |
15 |
Correct |
225 ms |
75120 KB |
Output is correct |
16 |
Correct |
223 ms |
74628 KB |
Output is correct |
17 |
Correct |
134 ms |
39368 KB |
Output is correct |
18 |
Correct |
25 ms |
29252 KB |
Output is correct |
19 |
Correct |
114 ms |
37340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
29160 KB |
Output is correct |
2 |
Correct |
393 ms |
151448 KB |
Output is correct |
3 |
Correct |
414 ms |
145616 KB |
Output is correct |
4 |
Correct |
458 ms |
168416 KB |
Output is correct |
5 |
Correct |
423 ms |
160464 KB |
Output is correct |
6 |
Correct |
37 ms |
31732 KB |
Output is correct |
7 |
Correct |
38 ms |
31868 KB |
Output is correct |
8 |
Correct |
38 ms |
31608 KB |
Output is correct |
9 |
Correct |
30 ms |
29376 KB |
Output is correct |
10 |
Correct |
26 ms |
29388 KB |
Output is correct |
11 |
Correct |
31 ms |
29504 KB |
Output is correct |
12 |
Correct |
263 ms |
112812 KB |
Output is correct |
13 |
Correct |
399 ms |
151132 KB |
Output is correct |
14 |
Correct |
26 ms |
29260 KB |
Output is correct |
15 |
Correct |
369 ms |
111544 KB |
Output is correct |
16 |
Correct |
384 ms |
120376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
29260 KB |
Output is correct |
2 |
Correct |
26 ms |
29388 KB |
Output is correct |
3 |
Correct |
25 ms |
29152 KB |
Output is correct |
4 |
Correct |
27 ms |
29372 KB |
Output is correct |
5 |
Correct |
26 ms |
29452 KB |
Output is correct |
6 |
Correct |
26 ms |
29256 KB |
Output is correct |
7 |
Correct |
26 ms |
29380 KB |
Output is correct |
8 |
Correct |
27 ms |
29320 KB |
Output is correct |
9 |
Correct |
27 ms |
29460 KB |
Output is correct |
10 |
Correct |
33 ms |
29384 KB |
Output is correct |
11 |
Correct |
33 ms |
29424 KB |
Output is correct |
12 |
Correct |
33 ms |
29500 KB |
Output is correct |
13 |
Correct |
36 ms |
29288 KB |
Output is correct |
14 |
Correct |
29 ms |
29448 KB |
Output is correct |
15 |
Correct |
26 ms |
29176 KB |
Output is correct |
16 |
Correct |
25 ms |
29260 KB |
Output is correct |
17 |
Correct |
30 ms |
29388 KB |
Output is correct |
18 |
Correct |
27 ms |
29320 KB |
Output is correct |
19 |
Correct |
31 ms |
29244 KB |
Output is correct |
20 |
Correct |
27 ms |
29188 KB |
Output is correct |
21 |
Correct |
35 ms |
29168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
29260 KB |
Output is correct |
2 |
Correct |
26 ms |
29388 KB |
Output is correct |
3 |
Correct |
25 ms |
29152 KB |
Output is correct |
4 |
Correct |
27 ms |
29372 KB |
Output is correct |
5 |
Correct |
26 ms |
29452 KB |
Output is correct |
6 |
Correct |
26 ms |
29256 KB |
Output is correct |
7 |
Correct |
26 ms |
29380 KB |
Output is correct |
8 |
Correct |
27 ms |
29320 KB |
Output is correct |
9 |
Correct |
27 ms |
29460 KB |
Output is correct |
10 |
Correct |
33 ms |
29384 KB |
Output is correct |
11 |
Correct |
33 ms |
29424 KB |
Output is correct |
12 |
Correct |
33 ms |
29500 KB |
Output is correct |
13 |
Correct |
36 ms |
29288 KB |
Output is correct |
14 |
Correct |
29 ms |
29448 KB |
Output is correct |
15 |
Correct |
26 ms |
29176 KB |
Output is correct |
16 |
Correct |
25 ms |
29260 KB |
Output is correct |
17 |
Correct |
30 ms |
29388 KB |
Output is correct |
18 |
Correct |
27 ms |
29320 KB |
Output is correct |
19 |
Correct |
31 ms |
29244 KB |
Output is correct |
20 |
Correct |
27 ms |
29188 KB |
Output is correct |
21 |
Correct |
35 ms |
29168 KB |
Output is correct |
22 |
Correct |
28 ms |
29136 KB |
Output is correct |
23 |
Correct |
36 ms |
30652 KB |
Output is correct |
24 |
Correct |
43 ms |
31476 KB |
Output is correct |
25 |
Correct |
34 ms |
30532 KB |
Output is correct |
26 |
Correct |
40 ms |
30056 KB |
Output is correct |
27 |
Correct |
33 ms |
30912 KB |
Output is correct |
28 |
Correct |
32 ms |
29368 KB |
Output is correct |
29 |
Correct |
35 ms |
31468 KB |
Output is correct |
30 |
Correct |
33 ms |
31180 KB |
Output is correct |
31 |
Correct |
36 ms |
29516 KB |
Output is correct |
32 |
Correct |
28 ms |
29416 KB |
Output is correct |
33 |
Correct |
37 ms |
31728 KB |
Output is correct |
34 |
Correct |
37 ms |
31848 KB |
Output is correct |
35 |
Correct |
36 ms |
31540 KB |
Output is correct |
36 |
Correct |
33 ms |
30496 KB |
Output is correct |
37 |
Correct |
32 ms |
30532 KB |
Output is correct |
38 |
Correct |
31 ms |
29380 KB |
Output is correct |
39 |
Correct |
26 ms |
29276 KB |
Output is correct |
40 |
Correct |
25 ms |
29232 KB |
Output is correct |
41 |
Correct |
25 ms |
29388 KB |
Output is correct |
42 |
Correct |
25 ms |
29432 KB |
Output is correct |
43 |
Correct |
25 ms |
29240 KB |
Output is correct |
44 |
Correct |
26 ms |
29468 KB |
Output is correct |
45 |
Correct |
25 ms |
29268 KB |
Output is correct |
46 |
Correct |
26 ms |
29420 KB |
Output is correct |
47 |
Correct |
30 ms |
29516 KB |
Output is correct |
48 |
Correct |
26 ms |
29484 KB |
Output is correct |
49 |
Correct |
30 ms |
29500 KB |
Output is correct |
50 |
Correct |
30 ms |
29340 KB |
Output is correct |
51 |
Correct |
31 ms |
29456 KB |
Output is correct |
52 |
Correct |
26 ms |
29260 KB |
Output is correct |
53 |
Correct |
42 ms |
30328 KB |
Output is correct |
54 |
Correct |
35 ms |
30576 KB |
Output is correct |
55 |
Correct |
32 ms |
29388 KB |
Output is correct |
56 |
Correct |
31 ms |
29416 KB |
Output is correct |
57 |
Correct |
31 ms |
29376 KB |
Output is correct |
58 |
Correct |
27 ms |
29252 KB |
Output is correct |
59 |
Correct |
26 ms |
29388 KB |
Output is correct |
60 |
Correct |
25 ms |
29260 KB |
Output is correct |
61 |
Correct |
26 ms |
29280 KB |
Output is correct |
62 |
Correct |
26 ms |
29260 KB |
Output is correct |
63 |
Correct |
27 ms |
29320 KB |
Output is correct |
64 |
Correct |
35 ms |
30284 KB |
Output is correct |
65 |
Correct |
35 ms |
30276 KB |
Output is correct |
66 |
Correct |
29 ms |
29408 KB |
Output is correct |
67 |
Correct |
28 ms |
29360 KB |
Output is correct |
68 |
Correct |
32 ms |
29384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
429 ms |
79152 KB |
Output is correct |
2 |
Correct |
387 ms |
78372 KB |
Output is correct |
3 |
Correct |
207 ms |
38976 KB |
Output is correct |
4 |
Correct |
410 ms |
81024 KB |
Output is correct |
5 |
Correct |
193 ms |
38940 KB |
Output is correct |
6 |
Correct |
186 ms |
38356 KB |
Output is correct |
7 |
Correct |
304 ms |
63936 KB |
Output is correct |
8 |
Correct |
115 ms |
37884 KB |
Output is correct |
9 |
Correct |
355 ms |
74100 KB |
Output is correct |
10 |
Correct |
380 ms |
70980 KB |
Output is correct |
11 |
Correct |
171 ms |
38852 KB |
Output is correct |
12 |
Correct |
169 ms |
38332 KB |
Output is correct |
13 |
Correct |
26 ms |
29260 KB |
Output is correct |
14 |
Correct |
343 ms |
111320 KB |
Output is correct |
15 |
Correct |
398 ms |
120400 KB |
Output is correct |
16 |
Correct |
35 ms |
30184 KB |
Output is correct |
17 |
Correct |
36 ms |
30184 KB |
Output is correct |
18 |
Correct |
28 ms |
29388 KB |
Output is correct |
19 |
Correct |
28 ms |
29392 KB |
Output is correct |
20 |
Correct |
32 ms |
29452 KB |
Output is correct |
21 |
Correct |
112 ms |
37336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
429 ms |
79152 KB |
Output is correct |
2 |
Correct |
387 ms |
78372 KB |
Output is correct |
3 |
Correct |
207 ms |
38976 KB |
Output is correct |
4 |
Correct |
410 ms |
81024 KB |
Output is correct |
5 |
Correct |
193 ms |
38940 KB |
Output is correct |
6 |
Correct |
186 ms |
38356 KB |
Output is correct |
7 |
Correct |
304 ms |
63936 KB |
Output is correct |
8 |
Correct |
115 ms |
37884 KB |
Output is correct |
9 |
Correct |
355 ms |
74100 KB |
Output is correct |
10 |
Correct |
380 ms |
70980 KB |
Output is correct |
11 |
Correct |
171 ms |
38852 KB |
Output is correct |
12 |
Correct |
169 ms |
38332 KB |
Output is correct |
13 |
Correct |
26 ms |
29260 KB |
Output is correct |
14 |
Correct |
343 ms |
111320 KB |
Output is correct |
15 |
Correct |
398 ms |
120400 KB |
Output is correct |
16 |
Correct |
35 ms |
30184 KB |
Output is correct |
17 |
Correct |
36 ms |
30184 KB |
Output is correct |
18 |
Correct |
28 ms |
29388 KB |
Output is correct |
19 |
Correct |
28 ms |
29392 KB |
Output is correct |
20 |
Correct |
32 ms |
29452 KB |
Output is correct |
21 |
Correct |
112 ms |
37336 KB |
Output is correct |
22 |
Correct |
25 ms |
29252 KB |
Output is correct |
23 |
Correct |
29 ms |
29136 KB |
Output is correct |
24 |
Correct |
26 ms |
29260 KB |
Output is correct |
25 |
Correct |
361 ms |
88656 KB |
Output is correct |
26 |
Correct |
319 ms |
82140 KB |
Output is correct |
27 |
Correct |
411 ms |
97488 KB |
Output is correct |
28 |
Correct |
177 ms |
39124 KB |
Output is correct |
29 |
Correct |
158 ms |
38380 KB |
Output is correct |
30 |
Correct |
160 ms |
37964 KB |
Output is correct |
31 |
Correct |
173 ms |
38156 KB |
Output is correct |
32 |
Correct |
376 ms |
80240 KB |
Output is correct |
33 |
Correct |
119 ms |
38024 KB |
Output is correct |
34 |
Correct |
289 ms |
70724 KB |
Output is correct |
35 |
Correct |
429 ms |
110488 KB |
Output is correct |
36 |
Correct |
163 ms |
39184 KB |
Output is correct |
37 |
Correct |
131 ms |
38320 KB |
Output is correct |
38 |
Correct |
255 ms |
112860 KB |
Output is correct |
39 |
Correct |
402 ms |
151144 KB |
Output is correct |
40 |
Correct |
34 ms |
30276 KB |
Output is correct |
41 |
Correct |
35 ms |
30572 KB |
Output is correct |
42 |
Correct |
32 ms |
29340 KB |
Output is correct |
43 |
Correct |
33 ms |
29384 KB |
Output is correct |
44 |
Correct |
32 ms |
29388 KB |
Output is correct |
45 |
Correct |
26 ms |
29268 KB |
Output is correct |
46 |
Correct |
26 ms |
29388 KB |
Output is correct |
47 |
Correct |
26 ms |
29260 KB |
Output is correct |
48 |
Correct |
26 ms |
29260 KB |
Output is correct |
49 |
Correct |
27 ms |
29260 KB |
Output is correct |
50 |
Correct |
87 ms |
34484 KB |
Output is correct |
51 |
Correct |
126 ms |
38084 KB |
Output is correct |
52 |
Correct |
412 ms |
79212 KB |
Output is correct |
53 |
Correct |
395 ms |
78272 KB |
Output is correct |
54 |
Correct |
203 ms |
39088 KB |
Output is correct |
55 |
Correct |
405 ms |
81112 KB |
Output is correct |
56 |
Correct |
193 ms |
38956 KB |
Output is correct |
57 |
Correct |
188 ms |
38348 KB |
Output is correct |
58 |
Correct |
320 ms |
64144 KB |
Output is correct |
59 |
Correct |
116 ms |
37852 KB |
Output is correct |
60 |
Correct |
360 ms |
73988 KB |
Output is correct |
61 |
Correct |
371 ms |
70948 KB |
Output is correct |
62 |
Correct |
173 ms |
38856 KB |
Output is correct |
63 |
Correct |
165 ms |
38280 KB |
Output is correct |
64 |
Correct |
25 ms |
29252 KB |
Output is correct |
65 |
Correct |
344 ms |
111324 KB |
Output is correct |
66 |
Correct |
390 ms |
120380 KB |
Output is correct |
67 |
Correct |
35 ms |
30192 KB |
Output is correct |
68 |
Correct |
38 ms |
30412 KB |
Output is correct |
69 |
Correct |
28 ms |
29380 KB |
Output is correct |
70 |
Correct |
27 ms |
29400 KB |
Output is correct |
71 |
Correct |
35 ms |
29412 KB |
Output is correct |
72 |
Correct |
116 ms |
37352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
29260 KB |
Output is correct |
2 |
Correct |
33 ms |
30512 KB |
Output is correct |
3 |
Correct |
32 ms |
30604 KB |
Output is correct |
4 |
Correct |
32 ms |
29456 KB |
Output is correct |
5 |
Correct |
31 ms |
29376 KB |
Output is correct |
6 |
Correct |
31 ms |
29468 KB |
Output is correct |
7 |
Correct |
25 ms |
29268 KB |
Output is correct |
8 |
Correct |
31 ms |
29384 KB |
Output is correct |
9 |
Correct |
32 ms |
29388 KB |
Output is correct |
10 |
Correct |
26 ms |
29240 KB |
Output is correct |
11 |
Correct |
25 ms |
29204 KB |
Output is correct |
12 |
Correct |
84 ms |
34564 KB |
Output is correct |
13 |
Correct |
121 ms |
38104 KB |
Output is correct |
14 |
Correct |
187 ms |
72100 KB |
Output is correct |
15 |
Correct |
225 ms |
75120 KB |
Output is correct |
16 |
Correct |
223 ms |
74628 KB |
Output is correct |
17 |
Correct |
134 ms |
39368 KB |
Output is correct |
18 |
Correct |
25 ms |
29252 KB |
Output is correct |
19 |
Correct |
114 ms |
37340 KB |
Output is correct |
20 |
Correct |
25 ms |
29160 KB |
Output is correct |
21 |
Correct |
393 ms |
151448 KB |
Output is correct |
22 |
Correct |
414 ms |
145616 KB |
Output is correct |
23 |
Correct |
458 ms |
168416 KB |
Output is correct |
24 |
Correct |
423 ms |
160464 KB |
Output is correct |
25 |
Correct |
37 ms |
31732 KB |
Output is correct |
26 |
Correct |
38 ms |
31868 KB |
Output is correct |
27 |
Correct |
38 ms |
31608 KB |
Output is correct |
28 |
Correct |
30 ms |
29376 KB |
Output is correct |
29 |
Correct |
26 ms |
29388 KB |
Output is correct |
30 |
Correct |
31 ms |
29504 KB |
Output is correct |
31 |
Correct |
263 ms |
112812 KB |
Output is correct |
32 |
Correct |
399 ms |
151132 KB |
Output is correct |
33 |
Correct |
26 ms |
29260 KB |
Output is correct |
34 |
Correct |
369 ms |
111544 KB |
Output is correct |
35 |
Correct |
384 ms |
120376 KB |
Output is correct |
36 |
Correct |
25 ms |
29260 KB |
Output is correct |
37 |
Correct |
26 ms |
29388 KB |
Output is correct |
38 |
Correct |
25 ms |
29152 KB |
Output is correct |
39 |
Correct |
27 ms |
29372 KB |
Output is correct |
40 |
Correct |
26 ms |
29452 KB |
Output is correct |
41 |
Correct |
26 ms |
29256 KB |
Output is correct |
42 |
Correct |
26 ms |
29380 KB |
Output is correct |
43 |
Correct |
27 ms |
29320 KB |
Output is correct |
44 |
Correct |
27 ms |
29460 KB |
Output is correct |
45 |
Correct |
33 ms |
29384 KB |
Output is correct |
46 |
Correct |
33 ms |
29424 KB |
Output is correct |
47 |
Correct |
33 ms |
29500 KB |
Output is correct |
48 |
Correct |
36 ms |
29288 KB |
Output is correct |
49 |
Correct |
29 ms |
29448 KB |
Output is correct |
50 |
Correct |
26 ms |
29176 KB |
Output is correct |
51 |
Correct |
25 ms |
29260 KB |
Output is correct |
52 |
Correct |
30 ms |
29388 KB |
Output is correct |
53 |
Correct |
27 ms |
29320 KB |
Output is correct |
54 |
Correct |
31 ms |
29244 KB |
Output is correct |
55 |
Correct |
27 ms |
29188 KB |
Output is correct |
56 |
Correct |
35 ms |
29168 KB |
Output is correct |
57 |
Correct |
28 ms |
29136 KB |
Output is correct |
58 |
Correct |
36 ms |
30652 KB |
Output is correct |
59 |
Correct |
43 ms |
31476 KB |
Output is correct |
60 |
Correct |
34 ms |
30532 KB |
Output is correct |
61 |
Correct |
40 ms |
30056 KB |
Output is correct |
62 |
Correct |
33 ms |
30912 KB |
Output is correct |
63 |
Correct |
32 ms |
29368 KB |
Output is correct |
64 |
Correct |
35 ms |
31468 KB |
Output is correct |
65 |
Correct |
33 ms |
31180 KB |
Output is correct |
66 |
Correct |
36 ms |
29516 KB |
Output is correct |
67 |
Correct |
28 ms |
29416 KB |
Output is correct |
68 |
Correct |
37 ms |
31728 KB |
Output is correct |
69 |
Correct |
37 ms |
31848 KB |
Output is correct |
70 |
Correct |
36 ms |
31540 KB |
Output is correct |
71 |
Correct |
33 ms |
30496 KB |
Output is correct |
72 |
Correct |
32 ms |
30532 KB |
Output is correct |
73 |
Correct |
31 ms |
29380 KB |
Output is correct |
74 |
Correct |
26 ms |
29276 KB |
Output is correct |
75 |
Correct |
25 ms |
29232 KB |
Output is correct |
76 |
Correct |
25 ms |
29388 KB |
Output is correct |
77 |
Correct |
25 ms |
29432 KB |
Output is correct |
78 |
Correct |
25 ms |
29240 KB |
Output is correct |
79 |
Correct |
26 ms |
29468 KB |
Output is correct |
80 |
Correct |
25 ms |
29268 KB |
Output is correct |
81 |
Correct |
26 ms |
29420 KB |
Output is correct |
82 |
Correct |
30 ms |
29516 KB |
Output is correct |
83 |
Correct |
26 ms |
29484 KB |
Output is correct |
84 |
Correct |
30 ms |
29500 KB |
Output is correct |
85 |
Correct |
30 ms |
29340 KB |
Output is correct |
86 |
Correct |
31 ms |
29456 KB |
Output is correct |
87 |
Correct |
26 ms |
29260 KB |
Output is correct |
88 |
Correct |
42 ms |
30328 KB |
Output is correct |
89 |
Correct |
35 ms |
30576 KB |
Output is correct |
90 |
Correct |
32 ms |
29388 KB |
Output is correct |
91 |
Correct |
31 ms |
29416 KB |
Output is correct |
92 |
Correct |
31 ms |
29376 KB |
Output is correct |
93 |
Correct |
27 ms |
29252 KB |
Output is correct |
94 |
Correct |
26 ms |
29388 KB |
Output is correct |
95 |
Correct |
25 ms |
29260 KB |
Output is correct |
96 |
Correct |
26 ms |
29280 KB |
Output is correct |
97 |
Correct |
26 ms |
29260 KB |
Output is correct |
98 |
Correct |
27 ms |
29320 KB |
Output is correct |
99 |
Correct |
35 ms |
30284 KB |
Output is correct |
100 |
Correct |
35 ms |
30276 KB |
Output is correct |
101 |
Correct |
29 ms |
29408 KB |
Output is correct |
102 |
Correct |
28 ms |
29360 KB |
Output is correct |
103 |
Correct |
32 ms |
29384 KB |
Output is correct |
104 |
Correct |
429 ms |
79152 KB |
Output is correct |
105 |
Correct |
387 ms |
78372 KB |
Output is correct |
106 |
Correct |
207 ms |
38976 KB |
Output is correct |
107 |
Correct |
410 ms |
81024 KB |
Output is correct |
108 |
Correct |
193 ms |
38940 KB |
Output is correct |
109 |
Correct |
186 ms |
38356 KB |
Output is correct |
110 |
Correct |
304 ms |
63936 KB |
Output is correct |
111 |
Correct |
115 ms |
37884 KB |
Output is correct |
112 |
Correct |
355 ms |
74100 KB |
Output is correct |
113 |
Correct |
380 ms |
70980 KB |
Output is correct |
114 |
Correct |
171 ms |
38852 KB |
Output is correct |
115 |
Correct |
169 ms |
38332 KB |
Output is correct |
116 |
Correct |
26 ms |
29260 KB |
Output is correct |
117 |
Correct |
343 ms |
111320 KB |
Output is correct |
118 |
Correct |
398 ms |
120400 KB |
Output is correct |
119 |
Correct |
35 ms |
30184 KB |
Output is correct |
120 |
Correct |
36 ms |
30184 KB |
Output is correct |
121 |
Correct |
28 ms |
29388 KB |
Output is correct |
122 |
Correct |
28 ms |
29392 KB |
Output is correct |
123 |
Correct |
32 ms |
29452 KB |
Output is correct |
124 |
Correct |
112 ms |
37336 KB |
Output is correct |
125 |
Correct |
25 ms |
29252 KB |
Output is correct |
126 |
Correct |
29 ms |
29136 KB |
Output is correct |
127 |
Correct |
26 ms |
29260 KB |
Output is correct |
128 |
Correct |
361 ms |
88656 KB |
Output is correct |
129 |
Correct |
319 ms |
82140 KB |
Output is correct |
130 |
Correct |
411 ms |
97488 KB |
Output is correct |
131 |
Correct |
177 ms |
39124 KB |
Output is correct |
132 |
Correct |
158 ms |
38380 KB |
Output is correct |
133 |
Correct |
160 ms |
37964 KB |
Output is correct |
134 |
Correct |
173 ms |
38156 KB |
Output is correct |
135 |
Correct |
376 ms |
80240 KB |
Output is correct |
136 |
Correct |
119 ms |
38024 KB |
Output is correct |
137 |
Correct |
289 ms |
70724 KB |
Output is correct |
138 |
Correct |
429 ms |
110488 KB |
Output is correct |
139 |
Correct |
163 ms |
39184 KB |
Output is correct |
140 |
Correct |
131 ms |
38320 KB |
Output is correct |
141 |
Correct |
255 ms |
112860 KB |
Output is correct |
142 |
Correct |
402 ms |
151144 KB |
Output is correct |
143 |
Correct |
34 ms |
30276 KB |
Output is correct |
144 |
Correct |
35 ms |
30572 KB |
Output is correct |
145 |
Correct |
32 ms |
29340 KB |
Output is correct |
146 |
Correct |
33 ms |
29384 KB |
Output is correct |
147 |
Correct |
32 ms |
29388 KB |
Output is correct |
148 |
Correct |
26 ms |
29268 KB |
Output is correct |
149 |
Correct |
26 ms |
29388 KB |
Output is correct |
150 |
Correct |
26 ms |
29260 KB |
Output is correct |
151 |
Correct |
26 ms |
29260 KB |
Output is correct |
152 |
Correct |
27 ms |
29260 KB |
Output is correct |
153 |
Correct |
87 ms |
34484 KB |
Output is correct |
154 |
Correct |
126 ms |
38084 KB |
Output is correct |
155 |
Correct |
412 ms |
79212 KB |
Output is correct |
156 |
Correct |
395 ms |
78272 KB |
Output is correct |
157 |
Correct |
203 ms |
39088 KB |
Output is correct |
158 |
Correct |
405 ms |
81112 KB |
Output is correct |
159 |
Correct |
193 ms |
38956 KB |
Output is correct |
160 |
Correct |
188 ms |
38348 KB |
Output is correct |
161 |
Correct |
320 ms |
64144 KB |
Output is correct |
162 |
Correct |
116 ms |
37852 KB |
Output is correct |
163 |
Correct |
360 ms |
73988 KB |
Output is correct |
164 |
Correct |
371 ms |
70948 KB |
Output is correct |
165 |
Correct |
173 ms |
38856 KB |
Output is correct |
166 |
Correct |
165 ms |
38280 KB |
Output is correct |
167 |
Correct |
25 ms |
29252 KB |
Output is correct |
168 |
Correct |
344 ms |
111324 KB |
Output is correct |
169 |
Correct |
390 ms |
120380 KB |
Output is correct |
170 |
Correct |
35 ms |
30192 KB |
Output is correct |
171 |
Correct |
38 ms |
30412 KB |
Output is correct |
172 |
Correct |
28 ms |
29380 KB |
Output is correct |
173 |
Correct |
27 ms |
29400 KB |
Output is correct |
174 |
Correct |
35 ms |
29412 KB |
Output is correct |
175 |
Correct |
116 ms |
37352 KB |
Output is correct |
176 |
Correct |
25 ms |
29156 KB |
Output is correct |
177 |
Correct |
532 ms |
148968 KB |
Output is correct |
178 |
Correct |
394 ms |
118476 KB |
Output is correct |
179 |
Correct |
210 ms |
39312 KB |
Output is correct |
180 |
Correct |
272 ms |
103636 KB |
Output is correct |
181 |
Correct |
204 ms |
39884 KB |
Output is correct |
182 |
Correct |
195 ms |
39504 KB |
Output is correct |
183 |
Correct |
321 ms |
70184 KB |
Output is correct |
184 |
Correct |
265 ms |
95976 KB |
Output is correct |
185 |
Correct |
271 ms |
96844 KB |
Output is correct |
186 |
Correct |
239 ms |
90068 KB |
Output is correct |
187 |
Correct |
215 ms |
74092 KB |
Output is correct |
188 |
Correct |
426 ms |
97820 KB |
Output is correct |
189 |
Correct |
395 ms |
94084 KB |
Output is correct |
190 |
Correct |
249 ms |
97600 KB |
Output is correct |
191 |
Correct |
183 ms |
39120 KB |
Output is correct |
192 |
Correct |
201 ms |
69852 KB |
Output is correct |
193 |
Correct |
252 ms |
90268 KB |
Output is correct |
194 |
Correct |
182 ms |
39908 KB |
Output is correct |
195 |
Correct |
403 ms |
151532 KB |
Output is correct |
196 |
Correct |
425 ms |
145652 KB |
Output is correct |
197 |
Correct |
466 ms |
168448 KB |
Output is correct |
198 |
Correct |
431 ms |
160380 KB |
Output is correct |
199 |
Correct |
40 ms |
30784 KB |
Output is correct |
200 |
Correct |
37 ms |
31596 KB |
Output is correct |
201 |
Correct |
39 ms |
30532 KB |
Output is correct |
202 |
Correct |
36 ms |
29976 KB |
Output is correct |
203 |
Correct |
34 ms |
30844 KB |
Output is correct |
204 |
Correct |
33 ms |
29380 KB |
Output is correct |
205 |
Correct |
35 ms |
31352 KB |
Output is correct |
206 |
Correct |
34 ms |
31220 KB |
Output is correct |
207 |
Correct |
34 ms |
29640 KB |
Output is correct |
208 |
Correct |
28 ms |
29416 KB |
Output is correct |
209 |
Correct |
37 ms |
31748 KB |
Output is correct |
210 |
Correct |
38 ms |
31868 KB |
Output is correct |
211 |
Correct |
37 ms |
31604 KB |
Output is correct |
212 |
Correct |
31 ms |
30456 KB |
Output is correct |
213 |
Correct |
35 ms |
30584 KB |
Output is correct |
214 |
Correct |
32 ms |
29488 KB |
Output is correct |
215 |
Correct |
26 ms |
29260 KB |
Output is correct |
216 |
Correct |
25 ms |
29164 KB |
Output is correct |
217 |
Correct |
27 ms |
29428 KB |
Output is correct |
218 |
Correct |
26 ms |
29400 KB |
Output is correct |
219 |
Correct |
26 ms |
29280 KB |
Output is correct |
220 |
Correct |
26 ms |
29388 KB |
Output is correct |
221 |
Correct |
28 ms |
29288 KB |
Output is correct |
222 |
Correct |
26 ms |
29372 KB |
Output is correct |
223 |
Correct |
30 ms |
29492 KB |
Output is correct |
224 |
Correct |
26 ms |
29388 KB |
Output is correct |
225 |
Correct |
31 ms |
29524 KB |
Output is correct |
226 |
Correct |
30 ms |
29268 KB |
Output is correct |
227 |
Correct |
30 ms |
29396 KB |
Output is correct |
228 |
Correct |
25 ms |
29216 KB |
Output is correct |
229 |
Correct |
364 ms |
88636 KB |
Output is correct |
230 |
Correct |
325 ms |
82008 KB |
Output is correct |
231 |
Correct |
425 ms |
97612 KB |
Output is correct |
232 |
Correct |
183 ms |
39300 KB |
Output is correct |
233 |
Correct |
158 ms |
38368 KB |
Output is correct |
234 |
Correct |
160 ms |
37956 KB |
Output is correct |
235 |
Correct |
169 ms |
38204 KB |
Output is correct |
236 |
Correct |
359 ms |
80168 KB |
Output is correct |
237 |
Correct |
118 ms |
38032 KB |
Output is correct |
238 |
Correct |
290 ms |
70716 KB |
Output is correct |
239 |
Correct |
418 ms |
110372 KB |
Output is correct |
240 |
Correct |
163 ms |
39112 KB |
Output is correct |
241 |
Correct |
135 ms |
38352 KB |
Output is correct |
242 |
Correct |
259 ms |
112904 KB |
Output is correct |
243 |
Correct |
408 ms |
151060 KB |
Output is correct |
244 |
Correct |
34 ms |
30332 KB |
Output is correct |
245 |
Correct |
36 ms |
30540 KB |
Output is correct |
246 |
Correct |
32 ms |
29400 KB |
Output is correct |
247 |
Correct |
31 ms |
29320 KB |
Output is correct |
248 |
Correct |
32 ms |
29360 KB |
Output is correct |
249 |
Correct |
25 ms |
29260 KB |
Output is correct |
250 |
Correct |
25 ms |
29400 KB |
Output is correct |
251 |
Correct |
26 ms |
29368 KB |
Output is correct |
252 |
Correct |
29 ms |
29172 KB |
Output is correct |
253 |
Correct |
26 ms |
29256 KB |
Output is correct |
254 |
Correct |
85 ms |
34528 KB |
Output is correct |
255 |
Correct |
122 ms |
38144 KB |
Output is correct |
256 |
Correct |
213 ms |
72220 KB |
Output is correct |
257 |
Correct |
213 ms |
75116 KB |
Output is correct |
258 |
Correct |
217 ms |
74768 KB |
Output is correct |
259 |
Correct |
132 ms |
39328 KB |
Output is correct |
260 |
Correct |
414 ms |
79320 KB |
Output is correct |
261 |
Correct |
395 ms |
78276 KB |
Output is correct |
262 |
Correct |
212 ms |
38988 KB |
Output is correct |
263 |
Correct |
409 ms |
81088 KB |
Output is correct |
264 |
Correct |
196 ms |
39004 KB |
Output is correct |
265 |
Correct |
189 ms |
38344 KB |
Output is correct |
266 |
Correct |
313 ms |
63984 KB |
Output is correct |
267 |
Correct |
124 ms |
37884 KB |
Output is correct |
268 |
Correct |
358 ms |
73992 KB |
Output is correct |
269 |
Correct |
398 ms |
71116 KB |
Output is correct |
270 |
Correct |
185 ms |
38884 KB |
Output is correct |
271 |
Correct |
156 ms |
38228 KB |
Output is correct |
272 |
Correct |
29 ms |
29380 KB |
Output is correct |
273 |
Correct |
352 ms |
111396 KB |
Output is correct |
274 |
Correct |
398 ms |
120440 KB |
Output is correct |
275 |
Correct |
36 ms |
30164 KB |
Output is correct |
276 |
Correct |
35 ms |
30304 KB |
Output is correct |
277 |
Correct |
29 ms |
29464 KB |
Output is correct |
278 |
Correct |
29 ms |
29392 KB |
Output is correct |
279 |
Correct |
33 ms |
29472 KB |
Output is correct |
280 |
Correct |
112 ms |
37432 KB |
Output is correct |