#include <bits/stdc++.h>
#include "roads.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
struct trie {
struct node {
int cnt; long long tot;
int ptr[2];
node (int _cnt = 0, long long _tot = 0) {
cnt = _cnt;
tot = _tot;
for (int i = 0; i < 2; i++)
ptr[i] = 0;
}
};
bool neg;
int num, sz;
vector <node> tree;
#define ptr(cur, i) tree[cur].ptr[i]
#define cnt(cur) tree[cur].cnt
#define tot(cur) tree[cur].tot
trie(int _neg = 0) {
neg = _neg;
num = 0;
sz = 0;
tree.emplace_back();
}
void add(long long x, int val) {
// cerr << "trie add " << x << " " << val << "\n";
sz += val;
x = abs(x);
int cur = 0;
for (int i = 60; i >= 0; i--) {
int v = getbit(x, i);
if (!ptr(cur, v)) {
ptr(cur, v) = ++num;
tree.emplace_back();
}
cur = ptr(cur, v);
cnt(cur) += val;
tot(cur) += (val > 0) ? x : -x;
}
}
long long getkth(int k) {
// cerr << "query " << k << "\n";
long long res = 0;
long long tmp = 0;
int cur = 0;
for (int i = 60; k > 0 && i >= 0; i--)
for (int v = 0; v < 2; v++) {
int p = ptr(cur, v ^ neg);
// cerr << cur << " " << (v ^ neg) << " " << p << "\n";
if (cnt(p) > k) {
if (v ^ neg)
tmp |= bit(i);
cur = p;
break;
}
k -= cnt(p);
res += tot(p);
}
// cerr << k << "\n";
if (k > 0)
res += k * tmp;
if (neg)
res = -res;
return res;
}
};
vector <int> adj[N];
vector <int> deg[N];
vector <int> g[N];
trie neg[N];
long long dp[N][2];
long long val[N];
int par[N];
int fr[N];
int to[N];
int h[N];
int w[N];
int n;
bool vis[N];
bool flag[N];
void dfs(int u, int p = -1) {
par[u] = p;
for (int i : adj[u]) {
int v = fr[i] ^ to[i] ^ u;
if (v == p)
continue;
dfs(v, u);
}
}
void addvalue(int v, long long x, int val) {
if (x < 0)
neg[v].add(x, val);
}
void add(int u) {
for (int i : adj[u]) {
int v = fr[i] ^ to[i] ^ u;
if (!flag[v]) {
val[u] += w[i];
addvalue(u, -w[i], 1);
continue;
}
val[v] -= w[i];
addvalue(v, -w[i], -1);
if (v == par[u])
g[v].push_back(i);
else
g[u].push_back(i);
}
flag[u] = true;
}
void solve(int u, int k) {
long long tot = val[u];
for (int i : g[u]) {
int v = fr[i] ^ to[i] ^ u;
solve(v, k);
tot += dp[v][1] + w[i];
addvalue(u, dp[v][0] - (dp[v][1] + w[i]), 1);
}
int cntneg = neg[u].sz;
// cerr << tot << "\n";
// cerr << cntneg << "\n";
if (cntneg >= k) {
dp[u][0] = neg[u].getkth(k - 1);
dp[u][1] = neg[u].getkth(k);
// cerr << dp[u][0] << " " << dp[u][1] << "\n";
} else
dp[u][0] = dp[u][1] = neg[u].getkth(cntneg);
dp[u][0] += tot;
dp[u][1] += tot;
for (int i : g[u]) {
int v = fr[i] ^ to[i] ^ u;
addvalue(u, dp[v][0] - (dp[v][1] + w[i]), -1);
}
}
vector <long long> solve() {
for (int i = 0; i < n; i++)
neg[i] = trie(1);
for (int i = 0; i < n - 1; i++) {
adj[fr[i]].push_back(i);
adj[to[i]].push_back(i);
}
for (int i = 0; i < n; i++)
deg[adj[i].size()].push_back(i);
dfs(1);
vector <long long> res;
vector <int> node;
for (int k = n - 1; k >= 1; k--) {
// cerr << "deg = " << k << "\n";
for (int v : deg[k]) {
add(v);
node.push_back(v);
// cerr << "add " << v << "\n";
}
long long tmp = 0;
for (int v : node) if (!flag[par[v]]) {
solve(v, k);
tmp += min(dp[v][0], dp[v][1]);
}
res.push_back(tmp);
}
res.push_back(accumulate(w, w + (n - 1), 0LL));
reverse(ALL(res));
return res;
}
vector<long long> minimum_closure_costs(int N, vector<int> U,
vector<int> V,
vector<int> W) {
n = N;
for (int i = 0; i < n - 1; i++) {
fr[i] = U[i];
to[i] = V[i];
w[i] = W[i];
}
return solve();
}
//#include "grader.cpp"
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14360 KB |
Output is correct |
2 |
Correct |
18 ms |
16208 KB |
Output is correct |
3 |
Correct |
18 ms |
16212 KB |
Output is correct |
4 |
Correct |
15 ms |
14676 KB |
Output is correct |
5 |
Correct |
13 ms |
14548 KB |
Output is correct |
6 |
Correct |
14 ms |
14676 KB |
Output is correct |
7 |
Correct |
12 ms |
14460 KB |
Output is correct |
8 |
Correct |
14 ms |
14536 KB |
Output is correct |
9 |
Correct |
16 ms |
14552 KB |
Output is correct |
10 |
Correct |
14 ms |
14344 KB |
Output is correct |
11 |
Correct |
12 ms |
14396 KB |
Output is correct |
12 |
Correct |
156 ms |
21412 KB |
Output is correct |
13 |
Correct |
258 ms |
25896 KB |
Output is correct |
14 |
Correct |
410 ms |
70980 KB |
Output is correct |
15 |
Correct |
503 ms |
71856 KB |
Output is correct |
16 |
Correct |
449 ms |
71808 KB |
Output is correct |
17 |
Correct |
289 ms |
26172 KB |
Output is correct |
18 |
Correct |
11 ms |
14384 KB |
Output is correct |
19 |
Correct |
222 ms |
24952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14420 KB |
Output is correct |
2 |
Correct |
412 ms |
253952 KB |
Output is correct |
3 |
Correct |
422 ms |
252144 KB |
Output is correct |
4 |
Correct |
465 ms |
290124 KB |
Output is correct |
5 |
Correct |
393 ms |
192948 KB |
Output is correct |
6 |
Correct |
20 ms |
19408 KB |
Output is correct |
7 |
Correct |
19 ms |
19540 KB |
Output is correct |
8 |
Correct |
19 ms |
17616 KB |
Output is correct |
9 |
Correct |
13 ms |
14804 KB |
Output is correct |
10 |
Correct |
13 ms |
14804 KB |
Output is correct |
11 |
Correct |
13 ms |
14676 KB |
Output is correct |
12 |
Correct |
275 ms |
172976 KB |
Output is correct |
13 |
Correct |
429 ms |
247640 KB |
Output is correct |
14 |
Correct |
10 ms |
14420 KB |
Output is correct |
15 |
Correct |
345 ms |
175412 KB |
Output is correct |
16 |
Correct |
368 ms |
193000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14376 KB |
Output is correct |
2 |
Correct |
11 ms |
14412 KB |
Output is correct |
3 |
Correct |
10 ms |
14420 KB |
Output is correct |
4 |
Correct |
13 ms |
14744 KB |
Output is correct |
5 |
Correct |
14 ms |
14804 KB |
Output is correct |
6 |
Correct |
12 ms |
14392 KB |
Output is correct |
7 |
Correct |
13 ms |
14676 KB |
Output is correct |
8 |
Correct |
13 ms |
14548 KB |
Output is correct |
9 |
Correct |
13 ms |
14752 KB |
Output is correct |
10 |
Correct |
12 ms |
14904 KB |
Output is correct |
11 |
Correct |
13 ms |
14804 KB |
Output is correct |
12 |
Correct |
12 ms |
14676 KB |
Output is correct |
13 |
Correct |
12 ms |
14548 KB |
Output is correct |
14 |
Correct |
11 ms |
14660 KB |
Output is correct |
15 |
Correct |
12 ms |
14420 KB |
Output is correct |
16 |
Correct |
12 ms |
14548 KB |
Output is correct |
17 |
Correct |
13 ms |
14628 KB |
Output is correct |
18 |
Correct |
12 ms |
14512 KB |
Output is correct |
19 |
Correct |
13 ms |
14520 KB |
Output is correct |
20 |
Correct |
14 ms |
14464 KB |
Output is correct |
21 |
Correct |
15 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14376 KB |
Output is correct |
2 |
Correct |
11 ms |
14412 KB |
Output is correct |
3 |
Correct |
10 ms |
14420 KB |
Output is correct |
4 |
Correct |
13 ms |
14744 KB |
Output is correct |
5 |
Correct |
14 ms |
14804 KB |
Output is correct |
6 |
Correct |
12 ms |
14392 KB |
Output is correct |
7 |
Correct |
13 ms |
14676 KB |
Output is correct |
8 |
Correct |
13 ms |
14548 KB |
Output is correct |
9 |
Correct |
13 ms |
14752 KB |
Output is correct |
10 |
Correct |
12 ms |
14904 KB |
Output is correct |
11 |
Correct |
13 ms |
14804 KB |
Output is correct |
12 |
Correct |
12 ms |
14676 KB |
Output is correct |
13 |
Correct |
12 ms |
14548 KB |
Output is correct |
14 |
Correct |
11 ms |
14660 KB |
Output is correct |
15 |
Correct |
12 ms |
14420 KB |
Output is correct |
16 |
Correct |
12 ms |
14548 KB |
Output is correct |
17 |
Correct |
13 ms |
14628 KB |
Output is correct |
18 |
Correct |
12 ms |
14512 KB |
Output is correct |
19 |
Correct |
13 ms |
14520 KB |
Output is correct |
20 |
Correct |
14 ms |
14464 KB |
Output is correct |
21 |
Correct |
15 ms |
14420 KB |
Output is correct |
22 |
Correct |
12 ms |
14420 KB |
Output is correct |
23 |
Correct |
18 ms |
17108 KB |
Output is correct |
24 |
Correct |
20 ms |
18836 KB |
Output is correct |
25 |
Correct |
21 ms |
17492 KB |
Output is correct |
26 |
Correct |
18 ms |
15828 KB |
Output is correct |
27 |
Correct |
19 ms |
16388 KB |
Output is correct |
28 |
Correct |
18 ms |
14724 KB |
Output is correct |
29 |
Correct |
19 ms |
18132 KB |
Output is correct |
30 |
Correct |
21 ms |
16564 KB |
Output is correct |
31 |
Correct |
18 ms |
14840 KB |
Output is correct |
32 |
Correct |
18 ms |
14716 KB |
Output is correct |
33 |
Correct |
23 ms |
19408 KB |
Output is correct |
34 |
Correct |
21 ms |
19668 KB |
Output is correct |
35 |
Correct |
19 ms |
17620 KB |
Output is correct |
36 |
Correct |
17 ms |
16208 KB |
Output is correct |
37 |
Correct |
17 ms |
16264 KB |
Output is correct |
38 |
Correct |
15 ms |
14676 KB |
Output is correct |
39 |
Correct |
12 ms |
14416 KB |
Output is correct |
40 |
Correct |
13 ms |
14420 KB |
Output is correct |
41 |
Correct |
15 ms |
14736 KB |
Output is correct |
42 |
Correct |
14 ms |
14804 KB |
Output is correct |
43 |
Correct |
15 ms |
14404 KB |
Output is correct |
44 |
Correct |
14 ms |
14832 KB |
Output is correct |
45 |
Correct |
15 ms |
14676 KB |
Output is correct |
46 |
Correct |
13 ms |
14668 KB |
Output is correct |
47 |
Correct |
13 ms |
14804 KB |
Output is correct |
48 |
Correct |
12 ms |
14804 KB |
Output is correct |
49 |
Correct |
13 ms |
14788 KB |
Output is correct |
50 |
Correct |
12 ms |
14552 KB |
Output is correct |
51 |
Correct |
12 ms |
14676 KB |
Output is correct |
52 |
Correct |
12 ms |
14420 KB |
Output is correct |
53 |
Correct |
20 ms |
16844 KB |
Output is correct |
54 |
Correct |
21 ms |
17608 KB |
Output is correct |
55 |
Correct |
19 ms |
14736 KB |
Output is correct |
56 |
Correct |
17 ms |
14540 KB |
Output is correct |
57 |
Correct |
15 ms |
14696 KB |
Output is correct |
58 |
Correct |
12 ms |
14548 KB |
Output is correct |
59 |
Correct |
12 ms |
14656 KB |
Output is correct |
60 |
Correct |
12 ms |
14528 KB |
Output is correct |
61 |
Correct |
12 ms |
14420 KB |
Output is correct |
62 |
Correct |
11 ms |
14516 KB |
Output is correct |
63 |
Correct |
11 ms |
14420 KB |
Output is correct |
64 |
Correct |
18 ms |
16316 KB |
Output is correct |
65 |
Correct |
19 ms |
16368 KB |
Output is correct |
66 |
Correct |
18 ms |
14800 KB |
Output is correct |
67 |
Correct |
16 ms |
14628 KB |
Output is correct |
68 |
Correct |
19 ms |
14676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
110128 KB |
Output is correct |
2 |
Correct |
517 ms |
108452 KB |
Output is correct |
3 |
Correct |
305 ms |
27104 KB |
Output is correct |
4 |
Correct |
498 ms |
113568 KB |
Output is correct |
5 |
Correct |
331 ms |
27140 KB |
Output is correct |
6 |
Correct |
301 ms |
26076 KB |
Output is correct |
7 |
Correct |
463 ms |
81544 KB |
Output is correct |
8 |
Correct |
261 ms |
25156 KB |
Output is correct |
9 |
Correct |
531 ms |
98992 KB |
Output is correct |
10 |
Correct |
507 ms |
96000 KB |
Output is correct |
11 |
Correct |
342 ms |
27336 KB |
Output is correct |
12 |
Correct |
271 ms |
26000 KB |
Output is correct |
13 |
Correct |
15 ms |
14420 KB |
Output is correct |
14 |
Correct |
370 ms |
175268 KB |
Output is correct |
15 |
Correct |
407 ms |
192972 KB |
Output is correct |
16 |
Correct |
23 ms |
16408 KB |
Output is correct |
17 |
Correct |
19 ms |
16340 KB |
Output is correct |
18 |
Correct |
18 ms |
14740 KB |
Output is correct |
19 |
Correct |
20 ms |
14692 KB |
Output is correct |
20 |
Correct |
18 ms |
14672 KB |
Output is correct |
21 |
Correct |
247 ms |
24872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
110128 KB |
Output is correct |
2 |
Correct |
517 ms |
108452 KB |
Output is correct |
3 |
Correct |
305 ms |
27104 KB |
Output is correct |
4 |
Correct |
498 ms |
113568 KB |
Output is correct |
5 |
Correct |
331 ms |
27140 KB |
Output is correct |
6 |
Correct |
301 ms |
26076 KB |
Output is correct |
7 |
Correct |
463 ms |
81544 KB |
Output is correct |
8 |
Correct |
261 ms |
25156 KB |
Output is correct |
9 |
Correct |
531 ms |
98992 KB |
Output is correct |
10 |
Correct |
507 ms |
96000 KB |
Output is correct |
11 |
Correct |
342 ms |
27336 KB |
Output is correct |
12 |
Correct |
271 ms |
26000 KB |
Output is correct |
13 |
Correct |
15 ms |
14420 KB |
Output is correct |
14 |
Correct |
370 ms |
175268 KB |
Output is correct |
15 |
Correct |
407 ms |
192972 KB |
Output is correct |
16 |
Correct |
23 ms |
16408 KB |
Output is correct |
17 |
Correct |
19 ms |
16340 KB |
Output is correct |
18 |
Correct |
18 ms |
14740 KB |
Output is correct |
19 |
Correct |
20 ms |
14692 KB |
Output is correct |
20 |
Correct |
18 ms |
14672 KB |
Output is correct |
21 |
Correct |
247 ms |
24872 KB |
Output is correct |
22 |
Correct |
12 ms |
14420 KB |
Output is correct |
23 |
Correct |
12 ms |
14332 KB |
Output is correct |
24 |
Correct |
12 ms |
14388 KB |
Output is correct |
25 |
Correct |
500 ms |
152424 KB |
Output is correct |
26 |
Correct |
465 ms |
136316 KB |
Output is correct |
27 |
Correct |
618 ms |
172456 KB |
Output is correct |
28 |
Correct |
329 ms |
27600 KB |
Output is correct |
29 |
Correct |
295 ms |
26660 KB |
Output is correct |
30 |
Correct |
306 ms |
25744 KB |
Output is correct |
31 |
Correct |
290 ms |
25816 KB |
Output is correct |
32 |
Correct |
495 ms |
107872 KB |
Output is correct |
33 |
Correct |
242 ms |
25296 KB |
Output is correct |
34 |
Correct |
473 ms |
102988 KB |
Output is correct |
35 |
Correct |
629 ms |
187400 KB |
Output is correct |
36 |
Correct |
341 ms |
27988 KB |
Output is correct |
37 |
Correct |
267 ms |
26064 KB |
Output is correct |
38 |
Correct |
280 ms |
172956 KB |
Output is correct |
39 |
Correct |
449 ms |
247620 KB |
Output is correct |
40 |
Correct |
18 ms |
16852 KB |
Output is correct |
41 |
Correct |
20 ms |
17548 KB |
Output is correct |
42 |
Correct |
17 ms |
14668 KB |
Output is correct |
43 |
Correct |
15 ms |
14556 KB |
Output is correct |
44 |
Correct |
16 ms |
14548 KB |
Output is correct |
45 |
Correct |
13 ms |
14548 KB |
Output is correct |
46 |
Correct |
13 ms |
14676 KB |
Output is correct |
47 |
Correct |
13 ms |
14508 KB |
Output is correct |
48 |
Correct |
12 ms |
14428 KB |
Output is correct |
49 |
Correct |
12 ms |
14420 KB |
Output is correct |
50 |
Correct |
168 ms |
21384 KB |
Output is correct |
51 |
Correct |
284 ms |
25920 KB |
Output is correct |
52 |
Correct |
463 ms |
110112 KB |
Output is correct |
53 |
Correct |
468 ms |
108308 KB |
Output is correct |
54 |
Correct |
298 ms |
27112 KB |
Output is correct |
55 |
Correct |
492 ms |
113732 KB |
Output is correct |
56 |
Correct |
301 ms |
27200 KB |
Output is correct |
57 |
Correct |
283 ms |
26064 KB |
Output is correct |
58 |
Correct |
378 ms |
81512 KB |
Output is correct |
59 |
Correct |
239 ms |
25188 KB |
Output is correct |
60 |
Correct |
443 ms |
99008 KB |
Output is correct |
61 |
Correct |
437 ms |
96020 KB |
Output is correct |
62 |
Correct |
290 ms |
27496 KB |
Output is correct |
63 |
Correct |
258 ms |
25996 KB |
Output is correct |
64 |
Correct |
11 ms |
14420 KB |
Output is correct |
65 |
Correct |
356 ms |
175192 KB |
Output is correct |
66 |
Correct |
377 ms |
192984 KB |
Output is correct |
67 |
Correct |
20 ms |
16372 KB |
Output is correct |
68 |
Correct |
20 ms |
16408 KB |
Output is correct |
69 |
Correct |
18 ms |
14724 KB |
Output is correct |
70 |
Correct |
19 ms |
14804 KB |
Output is correct |
71 |
Correct |
18 ms |
14748 KB |
Output is correct |
72 |
Correct |
223 ms |
24900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14360 KB |
Output is correct |
2 |
Correct |
18 ms |
16208 KB |
Output is correct |
3 |
Correct |
18 ms |
16212 KB |
Output is correct |
4 |
Correct |
15 ms |
14676 KB |
Output is correct |
5 |
Correct |
13 ms |
14548 KB |
Output is correct |
6 |
Correct |
14 ms |
14676 KB |
Output is correct |
7 |
Correct |
12 ms |
14460 KB |
Output is correct |
8 |
Correct |
14 ms |
14536 KB |
Output is correct |
9 |
Correct |
16 ms |
14552 KB |
Output is correct |
10 |
Correct |
14 ms |
14344 KB |
Output is correct |
11 |
Correct |
12 ms |
14396 KB |
Output is correct |
12 |
Correct |
156 ms |
21412 KB |
Output is correct |
13 |
Correct |
258 ms |
25896 KB |
Output is correct |
14 |
Correct |
410 ms |
70980 KB |
Output is correct |
15 |
Correct |
503 ms |
71856 KB |
Output is correct |
16 |
Correct |
449 ms |
71808 KB |
Output is correct |
17 |
Correct |
289 ms |
26172 KB |
Output is correct |
18 |
Correct |
11 ms |
14384 KB |
Output is correct |
19 |
Correct |
222 ms |
24952 KB |
Output is correct |
20 |
Correct |
11 ms |
14420 KB |
Output is correct |
21 |
Correct |
412 ms |
253952 KB |
Output is correct |
22 |
Correct |
422 ms |
252144 KB |
Output is correct |
23 |
Correct |
465 ms |
290124 KB |
Output is correct |
24 |
Correct |
393 ms |
192948 KB |
Output is correct |
25 |
Correct |
20 ms |
19408 KB |
Output is correct |
26 |
Correct |
19 ms |
19540 KB |
Output is correct |
27 |
Correct |
19 ms |
17616 KB |
Output is correct |
28 |
Correct |
13 ms |
14804 KB |
Output is correct |
29 |
Correct |
13 ms |
14804 KB |
Output is correct |
30 |
Correct |
13 ms |
14676 KB |
Output is correct |
31 |
Correct |
275 ms |
172976 KB |
Output is correct |
32 |
Correct |
429 ms |
247640 KB |
Output is correct |
33 |
Correct |
10 ms |
14420 KB |
Output is correct |
34 |
Correct |
345 ms |
175412 KB |
Output is correct |
35 |
Correct |
368 ms |
193000 KB |
Output is correct |
36 |
Correct |
11 ms |
14376 KB |
Output is correct |
37 |
Correct |
11 ms |
14412 KB |
Output is correct |
38 |
Correct |
10 ms |
14420 KB |
Output is correct |
39 |
Correct |
13 ms |
14744 KB |
Output is correct |
40 |
Correct |
14 ms |
14804 KB |
Output is correct |
41 |
Correct |
12 ms |
14392 KB |
Output is correct |
42 |
Correct |
13 ms |
14676 KB |
Output is correct |
43 |
Correct |
13 ms |
14548 KB |
Output is correct |
44 |
Correct |
13 ms |
14752 KB |
Output is correct |
45 |
Correct |
12 ms |
14904 KB |
Output is correct |
46 |
Correct |
13 ms |
14804 KB |
Output is correct |
47 |
Correct |
12 ms |
14676 KB |
Output is correct |
48 |
Correct |
12 ms |
14548 KB |
Output is correct |
49 |
Correct |
11 ms |
14660 KB |
Output is correct |
50 |
Correct |
12 ms |
14420 KB |
Output is correct |
51 |
Correct |
12 ms |
14548 KB |
Output is correct |
52 |
Correct |
13 ms |
14628 KB |
Output is correct |
53 |
Correct |
12 ms |
14512 KB |
Output is correct |
54 |
Correct |
13 ms |
14520 KB |
Output is correct |
55 |
Correct |
14 ms |
14464 KB |
Output is correct |
56 |
Correct |
15 ms |
14420 KB |
Output is correct |
57 |
Correct |
12 ms |
14420 KB |
Output is correct |
58 |
Correct |
18 ms |
17108 KB |
Output is correct |
59 |
Correct |
20 ms |
18836 KB |
Output is correct |
60 |
Correct |
21 ms |
17492 KB |
Output is correct |
61 |
Correct |
18 ms |
15828 KB |
Output is correct |
62 |
Correct |
19 ms |
16388 KB |
Output is correct |
63 |
Correct |
18 ms |
14724 KB |
Output is correct |
64 |
Correct |
19 ms |
18132 KB |
Output is correct |
65 |
Correct |
21 ms |
16564 KB |
Output is correct |
66 |
Correct |
18 ms |
14840 KB |
Output is correct |
67 |
Correct |
18 ms |
14716 KB |
Output is correct |
68 |
Correct |
23 ms |
19408 KB |
Output is correct |
69 |
Correct |
21 ms |
19668 KB |
Output is correct |
70 |
Correct |
19 ms |
17620 KB |
Output is correct |
71 |
Correct |
17 ms |
16208 KB |
Output is correct |
72 |
Correct |
17 ms |
16264 KB |
Output is correct |
73 |
Correct |
15 ms |
14676 KB |
Output is correct |
74 |
Correct |
12 ms |
14416 KB |
Output is correct |
75 |
Correct |
13 ms |
14420 KB |
Output is correct |
76 |
Correct |
15 ms |
14736 KB |
Output is correct |
77 |
Correct |
14 ms |
14804 KB |
Output is correct |
78 |
Correct |
15 ms |
14404 KB |
Output is correct |
79 |
Correct |
14 ms |
14832 KB |
Output is correct |
80 |
Correct |
15 ms |
14676 KB |
Output is correct |
81 |
Correct |
13 ms |
14668 KB |
Output is correct |
82 |
Correct |
13 ms |
14804 KB |
Output is correct |
83 |
Correct |
12 ms |
14804 KB |
Output is correct |
84 |
Correct |
13 ms |
14788 KB |
Output is correct |
85 |
Correct |
12 ms |
14552 KB |
Output is correct |
86 |
Correct |
12 ms |
14676 KB |
Output is correct |
87 |
Correct |
12 ms |
14420 KB |
Output is correct |
88 |
Correct |
20 ms |
16844 KB |
Output is correct |
89 |
Correct |
21 ms |
17608 KB |
Output is correct |
90 |
Correct |
19 ms |
14736 KB |
Output is correct |
91 |
Correct |
17 ms |
14540 KB |
Output is correct |
92 |
Correct |
15 ms |
14696 KB |
Output is correct |
93 |
Correct |
12 ms |
14548 KB |
Output is correct |
94 |
Correct |
12 ms |
14656 KB |
Output is correct |
95 |
Correct |
12 ms |
14528 KB |
Output is correct |
96 |
Correct |
12 ms |
14420 KB |
Output is correct |
97 |
Correct |
11 ms |
14516 KB |
Output is correct |
98 |
Correct |
11 ms |
14420 KB |
Output is correct |
99 |
Correct |
18 ms |
16316 KB |
Output is correct |
100 |
Correct |
19 ms |
16368 KB |
Output is correct |
101 |
Correct |
18 ms |
14800 KB |
Output is correct |
102 |
Correct |
16 ms |
14628 KB |
Output is correct |
103 |
Correct |
19 ms |
14676 KB |
Output is correct |
104 |
Correct |
530 ms |
110128 KB |
Output is correct |
105 |
Correct |
517 ms |
108452 KB |
Output is correct |
106 |
Correct |
305 ms |
27104 KB |
Output is correct |
107 |
Correct |
498 ms |
113568 KB |
Output is correct |
108 |
Correct |
331 ms |
27140 KB |
Output is correct |
109 |
Correct |
301 ms |
26076 KB |
Output is correct |
110 |
Correct |
463 ms |
81544 KB |
Output is correct |
111 |
Correct |
261 ms |
25156 KB |
Output is correct |
112 |
Correct |
531 ms |
98992 KB |
Output is correct |
113 |
Correct |
507 ms |
96000 KB |
Output is correct |
114 |
Correct |
342 ms |
27336 KB |
Output is correct |
115 |
Correct |
271 ms |
26000 KB |
Output is correct |
116 |
Correct |
15 ms |
14420 KB |
Output is correct |
117 |
Correct |
370 ms |
175268 KB |
Output is correct |
118 |
Correct |
407 ms |
192972 KB |
Output is correct |
119 |
Correct |
23 ms |
16408 KB |
Output is correct |
120 |
Correct |
19 ms |
16340 KB |
Output is correct |
121 |
Correct |
18 ms |
14740 KB |
Output is correct |
122 |
Correct |
20 ms |
14692 KB |
Output is correct |
123 |
Correct |
18 ms |
14672 KB |
Output is correct |
124 |
Correct |
247 ms |
24872 KB |
Output is correct |
125 |
Correct |
12 ms |
14420 KB |
Output is correct |
126 |
Correct |
12 ms |
14332 KB |
Output is correct |
127 |
Correct |
12 ms |
14388 KB |
Output is correct |
128 |
Correct |
500 ms |
152424 KB |
Output is correct |
129 |
Correct |
465 ms |
136316 KB |
Output is correct |
130 |
Correct |
618 ms |
172456 KB |
Output is correct |
131 |
Correct |
329 ms |
27600 KB |
Output is correct |
132 |
Correct |
295 ms |
26660 KB |
Output is correct |
133 |
Correct |
306 ms |
25744 KB |
Output is correct |
134 |
Correct |
290 ms |
25816 KB |
Output is correct |
135 |
Correct |
495 ms |
107872 KB |
Output is correct |
136 |
Correct |
242 ms |
25296 KB |
Output is correct |
137 |
Correct |
473 ms |
102988 KB |
Output is correct |
138 |
Correct |
629 ms |
187400 KB |
Output is correct |
139 |
Correct |
341 ms |
27988 KB |
Output is correct |
140 |
Correct |
267 ms |
26064 KB |
Output is correct |
141 |
Correct |
280 ms |
172956 KB |
Output is correct |
142 |
Correct |
449 ms |
247620 KB |
Output is correct |
143 |
Correct |
18 ms |
16852 KB |
Output is correct |
144 |
Correct |
20 ms |
17548 KB |
Output is correct |
145 |
Correct |
17 ms |
14668 KB |
Output is correct |
146 |
Correct |
15 ms |
14556 KB |
Output is correct |
147 |
Correct |
16 ms |
14548 KB |
Output is correct |
148 |
Correct |
13 ms |
14548 KB |
Output is correct |
149 |
Correct |
13 ms |
14676 KB |
Output is correct |
150 |
Correct |
13 ms |
14508 KB |
Output is correct |
151 |
Correct |
12 ms |
14428 KB |
Output is correct |
152 |
Correct |
12 ms |
14420 KB |
Output is correct |
153 |
Correct |
168 ms |
21384 KB |
Output is correct |
154 |
Correct |
284 ms |
25920 KB |
Output is correct |
155 |
Correct |
463 ms |
110112 KB |
Output is correct |
156 |
Correct |
468 ms |
108308 KB |
Output is correct |
157 |
Correct |
298 ms |
27112 KB |
Output is correct |
158 |
Correct |
492 ms |
113732 KB |
Output is correct |
159 |
Correct |
301 ms |
27200 KB |
Output is correct |
160 |
Correct |
283 ms |
26064 KB |
Output is correct |
161 |
Correct |
378 ms |
81512 KB |
Output is correct |
162 |
Correct |
239 ms |
25188 KB |
Output is correct |
163 |
Correct |
443 ms |
99008 KB |
Output is correct |
164 |
Correct |
437 ms |
96020 KB |
Output is correct |
165 |
Correct |
290 ms |
27496 KB |
Output is correct |
166 |
Correct |
258 ms |
25996 KB |
Output is correct |
167 |
Correct |
11 ms |
14420 KB |
Output is correct |
168 |
Correct |
356 ms |
175192 KB |
Output is correct |
169 |
Correct |
377 ms |
192984 KB |
Output is correct |
170 |
Correct |
20 ms |
16372 KB |
Output is correct |
171 |
Correct |
20 ms |
16408 KB |
Output is correct |
172 |
Correct |
18 ms |
14724 KB |
Output is correct |
173 |
Correct |
19 ms |
14804 KB |
Output is correct |
174 |
Correct |
18 ms |
14748 KB |
Output is correct |
175 |
Correct |
223 ms |
24900 KB |
Output is correct |
176 |
Correct |
14 ms |
14420 KB |
Output is correct |
177 |
Correct |
660 ms |
243048 KB |
Output is correct |
178 |
Correct |
483 ms |
184712 KB |
Output is correct |
179 |
Correct |
370 ms |
28972 KB |
Output is correct |
180 |
Correct |
443 ms |
102980 KB |
Output is correct |
181 |
Correct |
312 ms |
29460 KB |
Output is correct |
182 |
Correct |
330 ms |
28756 KB |
Output is correct |
183 |
Correct |
468 ms |
85928 KB |
Output is correct |
184 |
Correct |
523 ms |
91448 KB |
Output is correct |
185 |
Correct |
468 ms |
86188 KB |
Output is correct |
186 |
Correct |
437 ms |
87900 KB |
Output is correct |
187 |
Correct |
454 ms |
73868 KB |
Output is correct |
188 |
Correct |
571 ms |
133820 KB |
Output is correct |
189 |
Correct |
509 ms |
130520 KB |
Output is correct |
190 |
Correct |
445 ms |
91188 KB |
Output is correct |
191 |
Correct |
345 ms |
29380 KB |
Output is correct |
192 |
Correct |
432 ms |
66424 KB |
Output is correct |
193 |
Correct |
512 ms |
96336 KB |
Output is correct |
194 |
Correct |
279 ms |
29676 KB |
Output is correct |
195 |
Correct |
402 ms |
255768 KB |
Output is correct |
196 |
Correct |
428 ms |
253988 KB |
Output is correct |
197 |
Correct |
469 ms |
292144 KB |
Output is correct |
198 |
Correct |
376 ms |
195152 KB |
Output is correct |
199 |
Correct |
19 ms |
17216 KB |
Output is correct |
200 |
Correct |
21 ms |
18820 KB |
Output is correct |
201 |
Correct |
19 ms |
17492 KB |
Output is correct |
202 |
Correct |
18 ms |
15820 KB |
Output is correct |
203 |
Correct |
18 ms |
16420 KB |
Output is correct |
204 |
Correct |
17 ms |
14736 KB |
Output is correct |
205 |
Correct |
18 ms |
18044 KB |
Output is correct |
206 |
Correct |
20 ms |
16596 KB |
Output is correct |
207 |
Correct |
18 ms |
14844 KB |
Output is correct |
208 |
Correct |
20 ms |
14704 KB |
Output is correct |
209 |
Correct |
20 ms |
19380 KB |
Output is correct |
210 |
Correct |
22 ms |
19584 KB |
Output is correct |
211 |
Correct |
22 ms |
17652 KB |
Output is correct |
212 |
Correct |
18 ms |
16208 KB |
Output is correct |
213 |
Correct |
19 ms |
16212 KB |
Output is correct |
214 |
Correct |
18 ms |
14700 KB |
Output is correct |
215 |
Correct |
11 ms |
14364 KB |
Output is correct |
216 |
Correct |
11 ms |
14396 KB |
Output is correct |
217 |
Correct |
13 ms |
14804 KB |
Output is correct |
218 |
Correct |
13 ms |
14804 KB |
Output is correct |
219 |
Correct |
12 ms |
14420 KB |
Output is correct |
220 |
Correct |
15 ms |
14760 KB |
Output is correct |
221 |
Correct |
13 ms |
14548 KB |
Output is correct |
222 |
Correct |
13 ms |
14748 KB |
Output is correct |
223 |
Correct |
12 ms |
14804 KB |
Output is correct |
224 |
Correct |
15 ms |
14804 KB |
Output is correct |
225 |
Correct |
14 ms |
14796 KB |
Output is correct |
226 |
Correct |
12 ms |
14548 KB |
Output is correct |
227 |
Correct |
12 ms |
14676 KB |
Output is correct |
228 |
Correct |
11 ms |
14400 KB |
Output is correct |
229 |
Correct |
479 ms |
153608 KB |
Output is correct |
230 |
Correct |
435 ms |
137360 KB |
Output is correct |
231 |
Correct |
558 ms |
173840 KB |
Output is correct |
232 |
Correct |
341 ms |
29020 KB |
Output is correct |
233 |
Correct |
290 ms |
27864 KB |
Output is correct |
234 |
Correct |
293 ms |
26944 KB |
Output is correct |
235 |
Correct |
275 ms |
27164 KB |
Output is correct |
236 |
Correct |
462 ms |
109056 KB |
Output is correct |
237 |
Correct |
246 ms |
26592 KB |
Output is correct |
238 |
Correct |
451 ms |
104312 KB |
Output is correct |
239 |
Correct |
595 ms |
188780 KB |
Output is correct |
240 |
Correct |
282 ms |
29516 KB |
Output is correct |
241 |
Correct |
271 ms |
27312 KB |
Output is correct |
242 |
Correct |
268 ms |
173712 KB |
Output is correct |
243 |
Correct |
449 ms |
249036 KB |
Output is correct |
244 |
Correct |
18 ms |
16884 KB |
Output is correct |
245 |
Correct |
19 ms |
17516 KB |
Output is correct |
246 |
Correct |
16 ms |
14692 KB |
Output is correct |
247 |
Correct |
15 ms |
14604 KB |
Output is correct |
248 |
Correct |
15 ms |
14676 KB |
Output is correct |
249 |
Correct |
12 ms |
14548 KB |
Output is correct |
250 |
Correct |
13 ms |
14736 KB |
Output is correct |
251 |
Correct |
12 ms |
14548 KB |
Output is correct |
252 |
Correct |
12 ms |
14420 KB |
Output is correct |
253 |
Correct |
12 ms |
14420 KB |
Output is correct |
254 |
Correct |
155 ms |
22016 KB |
Output is correct |
255 |
Correct |
253 ms |
26808 KB |
Output is correct |
256 |
Correct |
413 ms |
72560 KB |
Output is correct |
257 |
Correct |
447 ms |
73476 KB |
Output is correct |
258 |
Correct |
477 ms |
73604 KB |
Output is correct |
259 |
Correct |
251 ms |
28064 KB |
Output is correct |
260 |
Correct |
447 ms |
111440 KB |
Output is correct |
261 |
Correct |
486 ms |
109648 KB |
Output is correct |
262 |
Correct |
275 ms |
28480 KB |
Output is correct |
263 |
Correct |
504 ms |
115024 KB |
Output is correct |
264 |
Correct |
288 ms |
28420 KB |
Output is correct |
265 |
Correct |
284 ms |
27424 KB |
Output is correct |
266 |
Correct |
381 ms |
82804 KB |
Output is correct |
267 |
Correct |
232 ms |
26500 KB |
Output is correct |
268 |
Correct |
432 ms |
100172 KB |
Output is correct |
269 |
Correct |
463 ms |
97352 KB |
Output is correct |
270 |
Correct |
271 ms |
28624 KB |
Output is correct |
271 |
Correct |
245 ms |
27364 KB |
Output is correct |
272 |
Correct |
11 ms |
14444 KB |
Output is correct |
273 |
Correct |
343 ms |
176476 KB |
Output is correct |
274 |
Correct |
365 ms |
194340 KB |
Output is correct |
275 |
Correct |
21 ms |
16340 KB |
Output is correct |
276 |
Correct |
22 ms |
16332 KB |
Output is correct |
277 |
Correct |
17 ms |
14796 KB |
Output is correct |
278 |
Correct |
16 ms |
14676 KB |
Output is correct |
279 |
Correct |
17 ms |
14668 KB |
Output is correct |
280 |
Correct |
220 ms |
25816 KB |
Output is correct |