#include <iostream>
#include <random>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
//Wrapper for generating random integers from [0, N[
class RandInt
{
static std::random_device rd;
static std::mt19937 gen;
std::uniform_int_distribution<ll> distrib;
public:
RandInt(ll N) : distrib(0, N - 1) {}
ll operator ()() { return distrib(gen); }
};
std::random_device RandInt::rd;
std::mt19937 RandInt::gen(rd());
//End of template
#include "roads.h"
#include <vector>
#include <utility>
#include <unordered_map>
#include <queue>
#include <algorithm>
//Treap
struct TreapNode
{
TreapNode(ll v) : value(v), priority(gen_prio()), sum(v) {}
~TreapNode() { delete left; delete right; }
ll value, priority;
int size = 1;
ll sum;
TreapNode *left = nullptr, *right = nullptr;
private:
static RandInt gen_prio;
};
const ll INFTY = 1LL << 62;
RandInt TreapNode::gen_prio(INFTY);
using Treap = TreapNode *;
using Treapair = std::pair<Treap, Treap>;
int size(Treap t)
{
if (t)
return t->size;
return 0;
}
ll sum(Treap t)
{
if (t)
return t->sum;
return 0;
}
Treapair cut(Treap t, ll v)
{
if (t == nullptr)
return { nullptr, nullptr };
if (t->value < v)
{
Treapair sub = cut(t->right, v);
t->right = sub.first;
t->size -= size(sub.second);
t->sum -= sum(sub.second);
return { t, sub.second };
}
else
{
Treapair sub = cut(t->left, v);
t->left = sub.second;
t->size -= size(sub.first);
t->sum -= sum(sub.first);
return { sub.first, t };
}
}
Treap merge(Treap l, Treap r)
{
if (l == nullptr)
return r;
if (r == nullptr)
return l;
if (l->priority > r->priority)
{
l->size += size(r);
l->sum += sum(r);
l->right = merge(l->right, r);
return l;
}
else
{
r->size += size(l);
r->sum += sum(l);
r->left = merge(l, r->left);
return r;
}
}
void insert(Treap &t, ll v)
{
Treapair split = cut(t, v);
t = merge(merge(split.first, new TreapNode(v)), split.second);
}
int cnt_range(Treap &t, ll a, ll b)
{
Treapair low = cut(t, a);
Treapair high = cut(low.second, b);
int res = size(high.first);
t = merge(low.first, merge(high.first, high.second));
return res;
}
ll sum_k(Treap &t, int k)
{
if (k <= 0)
return 0;
if (t == nullptr)
return INFTY;
if (k > size(t->left))
return sum(t->left) + t->value + sum_k(t->right, k - size(t->left) - 1);
return sum_k(t->left, k);
}
ll sum_k_range(Treap &t, ll a, ll b, int k)
{
Treapair low = cut(t, a);
Treapair high = cut(low.second, b);
ll res = sum_k(high.first, k);
t = merge(low.first, merge(high.first, high.second));
return res;
}
//Main code
const int MAXN = 1e5;
std::unordered_map<int, ll> tree[MAXN];
Treap dead_neighbors[MAXN];
int degree[MAXN];
int deg_order[MAXN];
bool seen[MAXN];
ll min_cuts[MAXN][2];
ll cut_children(int node, int parent, int maxdeg)
{
int remain = degree[node] - maxdeg;
std::priority_queue<ll> add_cost;
ll res = 0;
for (auto [child, _] : tree[node])
{
if (child != parent)
{
if (min_cuts[child][1] > min_cuts[child][0])
{
res += min_cuts[child][0];
add_cost.emplace(min_cuts[child][0] - min_cuts[child][1]);
}
else
{
res += min_cuts[child][1];
remain--;
}
}
}
ll previous_alive = 0;
while (remain > 0 && !add_cost.empty())
{
ll smallest_alive = -add_cost.top();
add_cost.pop();
int cnt_dead = cnt_range(dead_neighbors[node], previous_alive, smallest_alive);
if (cnt_dead < remain)
{
res += sum_k_range(dead_neighbors[node], previous_alive, smallest_alive, cnt_dead) + smallest_alive;
remain -= cnt_dead + 1;
}
else
{
res += sum_k_range(dead_neighbors[node], previous_alive, smallest_alive, remain);
remain = 0;
}
previous_alive = smallest_alive;
}
res += sum_k_range(dead_neighbors[node], previous_alive, INFTY, remain);
return res;
}
void compute_cuts(int node, int parent, int maxdeg)
{
seen[node] = true;
for (auto [child, _] : tree[node])
if (child != parent)
compute_cuts(child, node, maxdeg);
min_cuts[node][0] = cut_children(node, parent, maxdeg);
if (parent != -1)
min_cuts[node][1] = cut_children(node, parent, maxdeg + 1) + tree[node][parent];
}
std::vector<ll> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for (int iEdge = 0; iEdge < N - 1; iEdge++)
{
tree[U[iEdge]][V[iEdge]] = W[iEdge];
tree[V[iEdge]][U[iEdge]] = W[iEdge];
}
for (int iNode = 0; iNode < N; iNode++)
{
dead_neighbors[iNode] = nullptr;
degree[iNode] = tree[iNode].size();
deg_order[iNode] = iNode;
seen[iNode] = false;
}
std::sort(deg_order, deg_order + N, [](int u, int v) { return degree[u] < degree[v]; });
int first_alive = 0;
std::vector<ll> ans(N, 0);
for (int maxdeg = 0; maxdeg < N; maxdeg++)
{
while (first_alive < N && degree[deg_order[first_alive]] <= maxdeg)
{
for (auto [neighbor, weight] : tree[deg_order[first_alive]])
{
tree[neighbor].erase(tree[neighbor].find(deg_order[first_alive]));
insert(dead_neighbors[neighbor], weight);
}
first_alive++;
}
for (int iNode = first_alive; iNode < N; iNode++)
if (!seen[deg_order[iNode]])
{
compute_cuts(deg_order[iNode], -1, maxdeg);
ans[maxdeg] += min_cuts[deg_order[iNode]][0];
}
for (int iNode = first_alive; iNode < N; iNode++)
seen[deg_order[iNode]] = false;
}
for (int iNode = 0; iNode < N; iNode++)
delete dead_neighbors[iNode];
return ans;
}
Compilation message
roads.cpp: In function 'll cut_children(int, int, int)':
roads.cpp:165:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
165 | for (auto [child, _] : tree[node])
| ^
roads.cpp: In function 'void compute_cuts(int, int, int)':
roads.cpp:210:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
210 | for (auto [child, _] : tree[node])
| ^
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:243:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
243 | for (auto [neighbor, weight] : tree[deg_order[first_alive]])
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
6 ms |
6356 KB |
Output is correct |
3 |
Correct |
6 ms |
6356 KB |
Output is correct |
4 |
Correct |
6 ms |
6356 KB |
Output is correct |
5 |
Correct |
3 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
3 ms |
5844 KB |
Output is correct |
8 |
Correct |
7 ms |
6400 KB |
Output is correct |
9 |
Correct |
6 ms |
6356 KB |
Output is correct |
10 |
Correct |
4 ms |
5844 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
145 ms |
24412 KB |
Output is correct |
13 |
Correct |
244 ms |
36984 KB |
Output is correct |
14 |
Correct |
269 ms |
34076 KB |
Output is correct |
15 |
Correct |
321 ms |
36760 KB |
Output is correct |
16 |
Correct |
325 ms |
37360 KB |
Output is correct |
17 |
Correct |
263 ms |
37288 KB |
Output is correct |
18 |
Correct |
4 ms |
5716 KB |
Output is correct |
19 |
Correct |
215 ms |
34228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
107 ms |
35828 KB |
Output is correct |
3 |
Correct |
123 ms |
40840 KB |
Output is correct |
4 |
Correct |
131 ms |
43144 KB |
Output is correct |
5 |
Correct |
136 ms |
43220 KB |
Output is correct |
6 |
Correct |
5 ms |
6356 KB |
Output is correct |
7 |
Correct |
6 ms |
6444 KB |
Output is correct |
8 |
Correct |
6 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
5844 KB |
Output is correct |
10 |
Correct |
3 ms |
5796 KB |
Output is correct |
11 |
Correct |
3 ms |
5844 KB |
Output is correct |
12 |
Correct |
75 ms |
28248 KB |
Output is correct |
13 |
Correct |
130 ms |
43188 KB |
Output is correct |
14 |
Correct |
4 ms |
5788 KB |
Output is correct |
15 |
Correct |
108 ms |
39464 KB |
Output is correct |
16 |
Correct |
122 ms |
43176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5796 KB |
Output is correct |
4 |
Correct |
4 ms |
5844 KB |
Output is correct |
5 |
Correct |
4 ms |
5844 KB |
Output is correct |
6 |
Correct |
5 ms |
5796 KB |
Output is correct |
7 |
Correct |
4 ms |
5908 KB |
Output is correct |
8 |
Correct |
5 ms |
5800 KB |
Output is correct |
9 |
Correct |
4 ms |
5796 KB |
Output is correct |
10 |
Correct |
3 ms |
5796 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5796 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
4 ms |
5844 KB |
Output is correct |
15 |
Correct |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
4 ms |
5844 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
5 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5796 KB |
Output is correct |
4 |
Correct |
4 ms |
5844 KB |
Output is correct |
5 |
Correct |
4 ms |
5844 KB |
Output is correct |
6 |
Correct |
5 ms |
5796 KB |
Output is correct |
7 |
Correct |
4 ms |
5908 KB |
Output is correct |
8 |
Correct |
5 ms |
5800 KB |
Output is correct |
9 |
Correct |
4 ms |
5796 KB |
Output is correct |
10 |
Correct |
3 ms |
5796 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5796 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
4 ms |
5844 KB |
Output is correct |
15 |
Correct |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
4 ms |
5844 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
5 ms |
5716 KB |
Output is correct |
22 |
Correct |
3 ms |
5716 KB |
Output is correct |
23 |
Correct |
5 ms |
6188 KB |
Output is correct |
24 |
Correct |
6 ms |
6356 KB |
Output is correct |
25 |
Correct |
7 ms |
6344 KB |
Output is correct |
26 |
Correct |
6 ms |
6448 KB |
Output is correct |
27 |
Correct |
7 ms |
6484 KB |
Output is correct |
28 |
Correct |
7 ms |
6476 KB |
Output is correct |
29 |
Correct |
7 ms |
6452 KB |
Output is correct |
30 |
Correct |
7 ms |
6448 KB |
Output is correct |
31 |
Correct |
6 ms |
6448 KB |
Output is correct |
32 |
Correct |
6 ms |
6356 KB |
Output is correct |
33 |
Correct |
6 ms |
6356 KB |
Output is correct |
34 |
Correct |
7 ms |
6572 KB |
Output is correct |
35 |
Correct |
6 ms |
6484 KB |
Output is correct |
36 |
Correct |
7 ms |
6452 KB |
Output is correct |
37 |
Correct |
7 ms |
6384 KB |
Output is correct |
38 |
Correct |
6 ms |
6476 KB |
Output is correct |
39 |
Correct |
3 ms |
5800 KB |
Output is correct |
40 |
Correct |
4 ms |
5716 KB |
Output is correct |
41 |
Correct |
4 ms |
5844 KB |
Output is correct |
42 |
Correct |
4 ms |
5844 KB |
Output is correct |
43 |
Correct |
4 ms |
5844 KB |
Output is correct |
44 |
Correct |
4 ms |
5844 KB |
Output is correct |
45 |
Correct |
4 ms |
5844 KB |
Output is correct |
46 |
Correct |
4 ms |
5844 KB |
Output is correct |
47 |
Correct |
4 ms |
5844 KB |
Output is correct |
48 |
Correct |
4 ms |
5844 KB |
Output is correct |
49 |
Correct |
4 ms |
5844 KB |
Output is correct |
50 |
Correct |
4 ms |
5844 KB |
Output is correct |
51 |
Correct |
4 ms |
5792 KB |
Output is correct |
52 |
Correct |
5 ms |
5844 KB |
Output is correct |
53 |
Correct |
6 ms |
6228 KB |
Output is correct |
54 |
Correct |
6 ms |
6316 KB |
Output is correct |
55 |
Correct |
7 ms |
6356 KB |
Output is correct |
56 |
Correct |
5 ms |
6316 KB |
Output is correct |
57 |
Correct |
6 ms |
6356 KB |
Output is correct |
58 |
Correct |
3 ms |
5796 KB |
Output is correct |
59 |
Correct |
4 ms |
5844 KB |
Output is correct |
60 |
Correct |
4 ms |
5844 KB |
Output is correct |
61 |
Correct |
4 ms |
5844 KB |
Output is correct |
62 |
Correct |
4 ms |
5800 KB |
Output is correct |
63 |
Correct |
4 ms |
5796 KB |
Output is correct |
64 |
Correct |
6 ms |
6356 KB |
Output is correct |
65 |
Correct |
7 ms |
6356 KB |
Output is correct |
66 |
Correct |
7 ms |
6352 KB |
Output is correct |
67 |
Correct |
7 ms |
6356 KB |
Output is correct |
68 |
Correct |
6 ms |
6356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
278 ms |
34004 KB |
Output is correct |
2 |
Correct |
276 ms |
34876 KB |
Output is correct |
3 |
Correct |
312 ms |
38260 KB |
Output is correct |
4 |
Correct |
278 ms |
36232 KB |
Output is correct |
5 |
Correct |
320 ms |
38280 KB |
Output is correct |
6 |
Correct |
297 ms |
37880 KB |
Output is correct |
7 |
Correct |
282 ms |
37404 KB |
Output is correct |
8 |
Correct |
200 ms |
35904 KB |
Output is correct |
9 |
Correct |
248 ms |
36172 KB |
Output is correct |
10 |
Correct |
275 ms |
35752 KB |
Output is correct |
11 |
Correct |
308 ms |
38104 KB |
Output is correct |
12 |
Correct |
258 ms |
38316 KB |
Output is correct |
13 |
Correct |
3 ms |
5716 KB |
Output is correct |
14 |
Correct |
117 ms |
39484 KB |
Output is correct |
15 |
Correct |
126 ms |
43236 KB |
Output is correct |
16 |
Correct |
6 ms |
6356 KB |
Output is correct |
17 |
Correct |
5 ms |
6352 KB |
Output is correct |
18 |
Correct |
6 ms |
6356 KB |
Output is correct |
19 |
Correct |
6 ms |
6356 KB |
Output is correct |
20 |
Correct |
7 ms |
6356 KB |
Output is correct |
21 |
Correct |
210 ms |
34992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
278 ms |
34004 KB |
Output is correct |
2 |
Correct |
276 ms |
34876 KB |
Output is correct |
3 |
Correct |
312 ms |
38260 KB |
Output is correct |
4 |
Correct |
278 ms |
36232 KB |
Output is correct |
5 |
Correct |
320 ms |
38280 KB |
Output is correct |
6 |
Correct |
297 ms |
37880 KB |
Output is correct |
7 |
Correct |
282 ms |
37404 KB |
Output is correct |
8 |
Correct |
200 ms |
35904 KB |
Output is correct |
9 |
Correct |
248 ms |
36172 KB |
Output is correct |
10 |
Correct |
275 ms |
35752 KB |
Output is correct |
11 |
Correct |
308 ms |
38104 KB |
Output is correct |
12 |
Correct |
258 ms |
38316 KB |
Output is correct |
13 |
Correct |
3 ms |
5716 KB |
Output is correct |
14 |
Correct |
117 ms |
39484 KB |
Output is correct |
15 |
Correct |
126 ms |
43236 KB |
Output is correct |
16 |
Correct |
6 ms |
6356 KB |
Output is correct |
17 |
Correct |
5 ms |
6352 KB |
Output is correct |
18 |
Correct |
6 ms |
6356 KB |
Output is correct |
19 |
Correct |
6 ms |
6356 KB |
Output is correct |
20 |
Correct |
7 ms |
6356 KB |
Output is correct |
21 |
Correct |
210 ms |
34992 KB |
Output is correct |
22 |
Correct |
4 ms |
5796 KB |
Output is correct |
23 |
Correct |
3 ms |
5716 KB |
Output is correct |
24 |
Correct |
3 ms |
5796 KB |
Output is correct |
25 |
Correct |
244 ms |
31948 KB |
Output is correct |
26 |
Correct |
214 ms |
29388 KB |
Output is correct |
27 |
Correct |
304 ms |
36268 KB |
Output is correct |
28 |
Correct |
363 ms |
38356 KB |
Output is correct |
29 |
Correct |
317 ms |
35756 KB |
Output is correct |
30 |
Correct |
326 ms |
36720 KB |
Output is correct |
31 |
Correct |
340 ms |
38036 KB |
Output is correct |
32 |
Correct |
282 ms |
34152 KB |
Output is correct |
33 |
Correct |
220 ms |
36648 KB |
Output is correct |
34 |
Correct |
327 ms |
37448 KB |
Output is correct |
35 |
Correct |
293 ms |
39036 KB |
Output is correct |
36 |
Correct |
336 ms |
38120 KB |
Output is correct |
37 |
Correct |
305 ms |
38328 KB |
Output is correct |
38 |
Correct |
81 ms |
28200 KB |
Output is correct |
39 |
Correct |
124 ms |
43128 KB |
Output is correct |
40 |
Correct |
6 ms |
6228 KB |
Output is correct |
41 |
Correct |
6 ms |
6376 KB |
Output is correct |
42 |
Correct |
8 ms |
6356 KB |
Output is correct |
43 |
Correct |
6 ms |
6356 KB |
Output is correct |
44 |
Correct |
6 ms |
6356 KB |
Output is correct |
45 |
Correct |
3 ms |
5792 KB |
Output is correct |
46 |
Correct |
4 ms |
5844 KB |
Output is correct |
47 |
Correct |
4 ms |
5796 KB |
Output is correct |
48 |
Correct |
4 ms |
5844 KB |
Output is correct |
49 |
Correct |
4 ms |
5844 KB |
Output is correct |
50 |
Correct |
132 ms |
24928 KB |
Output is correct |
51 |
Correct |
246 ms |
37944 KB |
Output is correct |
52 |
Correct |
293 ms |
35280 KB |
Output is correct |
53 |
Correct |
257 ms |
34688 KB |
Output is correct |
54 |
Correct |
308 ms |
38368 KB |
Output is correct |
55 |
Correct |
272 ms |
36284 KB |
Output is correct |
56 |
Correct |
364 ms |
38264 KB |
Output is correct |
57 |
Correct |
291 ms |
37912 KB |
Output is correct |
58 |
Correct |
278 ms |
37400 KB |
Output is correct |
59 |
Correct |
198 ms |
35880 KB |
Output is correct |
60 |
Correct |
266 ms |
36180 KB |
Output is correct |
61 |
Correct |
288 ms |
35736 KB |
Output is correct |
62 |
Correct |
287 ms |
38064 KB |
Output is correct |
63 |
Correct |
287 ms |
38288 KB |
Output is correct |
64 |
Correct |
4 ms |
5716 KB |
Output is correct |
65 |
Correct |
112 ms |
39528 KB |
Output is correct |
66 |
Correct |
137 ms |
43128 KB |
Output is correct |
67 |
Correct |
6 ms |
6356 KB |
Output is correct |
68 |
Correct |
6 ms |
6320 KB |
Output is correct |
69 |
Correct |
7 ms |
6356 KB |
Output is correct |
70 |
Correct |
6 ms |
6452 KB |
Output is correct |
71 |
Correct |
8 ms |
6356 KB |
Output is correct |
72 |
Correct |
189 ms |
34988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
6 ms |
6356 KB |
Output is correct |
3 |
Correct |
6 ms |
6356 KB |
Output is correct |
4 |
Correct |
6 ms |
6356 KB |
Output is correct |
5 |
Correct |
3 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
3 ms |
5844 KB |
Output is correct |
8 |
Correct |
7 ms |
6400 KB |
Output is correct |
9 |
Correct |
6 ms |
6356 KB |
Output is correct |
10 |
Correct |
4 ms |
5844 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
145 ms |
24412 KB |
Output is correct |
13 |
Correct |
244 ms |
36984 KB |
Output is correct |
14 |
Correct |
269 ms |
34076 KB |
Output is correct |
15 |
Correct |
321 ms |
36760 KB |
Output is correct |
16 |
Correct |
325 ms |
37360 KB |
Output is correct |
17 |
Correct |
263 ms |
37288 KB |
Output is correct |
18 |
Correct |
4 ms |
5716 KB |
Output is correct |
19 |
Correct |
215 ms |
34228 KB |
Output is correct |
20 |
Correct |
3 ms |
5716 KB |
Output is correct |
21 |
Correct |
107 ms |
35828 KB |
Output is correct |
22 |
Correct |
123 ms |
40840 KB |
Output is correct |
23 |
Correct |
131 ms |
43144 KB |
Output is correct |
24 |
Correct |
136 ms |
43220 KB |
Output is correct |
25 |
Correct |
5 ms |
6356 KB |
Output is correct |
26 |
Correct |
6 ms |
6444 KB |
Output is correct |
27 |
Correct |
6 ms |
6484 KB |
Output is correct |
28 |
Correct |
4 ms |
5844 KB |
Output is correct |
29 |
Correct |
3 ms |
5796 KB |
Output is correct |
30 |
Correct |
3 ms |
5844 KB |
Output is correct |
31 |
Correct |
75 ms |
28248 KB |
Output is correct |
32 |
Correct |
130 ms |
43188 KB |
Output is correct |
33 |
Correct |
4 ms |
5788 KB |
Output is correct |
34 |
Correct |
108 ms |
39464 KB |
Output is correct |
35 |
Correct |
122 ms |
43176 KB |
Output is correct |
36 |
Correct |
3 ms |
5716 KB |
Output is correct |
37 |
Correct |
3 ms |
5708 KB |
Output is correct |
38 |
Correct |
4 ms |
5796 KB |
Output is correct |
39 |
Correct |
4 ms |
5844 KB |
Output is correct |
40 |
Correct |
4 ms |
5844 KB |
Output is correct |
41 |
Correct |
5 ms |
5796 KB |
Output is correct |
42 |
Correct |
4 ms |
5908 KB |
Output is correct |
43 |
Correct |
5 ms |
5800 KB |
Output is correct |
44 |
Correct |
4 ms |
5796 KB |
Output is correct |
45 |
Correct |
3 ms |
5796 KB |
Output is correct |
46 |
Correct |
4 ms |
5844 KB |
Output is correct |
47 |
Correct |
4 ms |
5796 KB |
Output is correct |
48 |
Correct |
4 ms |
5844 KB |
Output is correct |
49 |
Correct |
4 ms |
5844 KB |
Output is correct |
50 |
Correct |
4 ms |
5844 KB |
Output is correct |
51 |
Correct |
4 ms |
5844 KB |
Output is correct |
52 |
Correct |
4 ms |
5844 KB |
Output is correct |
53 |
Correct |
4 ms |
5844 KB |
Output is correct |
54 |
Correct |
4 ms |
5844 KB |
Output is correct |
55 |
Correct |
4 ms |
5844 KB |
Output is correct |
56 |
Correct |
5 ms |
5716 KB |
Output is correct |
57 |
Correct |
3 ms |
5716 KB |
Output is correct |
58 |
Correct |
5 ms |
6188 KB |
Output is correct |
59 |
Correct |
6 ms |
6356 KB |
Output is correct |
60 |
Correct |
7 ms |
6344 KB |
Output is correct |
61 |
Correct |
6 ms |
6448 KB |
Output is correct |
62 |
Correct |
7 ms |
6484 KB |
Output is correct |
63 |
Correct |
7 ms |
6476 KB |
Output is correct |
64 |
Correct |
7 ms |
6452 KB |
Output is correct |
65 |
Correct |
7 ms |
6448 KB |
Output is correct |
66 |
Correct |
6 ms |
6448 KB |
Output is correct |
67 |
Correct |
6 ms |
6356 KB |
Output is correct |
68 |
Correct |
6 ms |
6356 KB |
Output is correct |
69 |
Correct |
7 ms |
6572 KB |
Output is correct |
70 |
Correct |
6 ms |
6484 KB |
Output is correct |
71 |
Correct |
7 ms |
6452 KB |
Output is correct |
72 |
Correct |
7 ms |
6384 KB |
Output is correct |
73 |
Correct |
6 ms |
6476 KB |
Output is correct |
74 |
Correct |
3 ms |
5800 KB |
Output is correct |
75 |
Correct |
4 ms |
5716 KB |
Output is correct |
76 |
Correct |
4 ms |
5844 KB |
Output is correct |
77 |
Correct |
4 ms |
5844 KB |
Output is correct |
78 |
Correct |
4 ms |
5844 KB |
Output is correct |
79 |
Correct |
4 ms |
5844 KB |
Output is correct |
80 |
Correct |
4 ms |
5844 KB |
Output is correct |
81 |
Correct |
4 ms |
5844 KB |
Output is correct |
82 |
Correct |
4 ms |
5844 KB |
Output is correct |
83 |
Correct |
4 ms |
5844 KB |
Output is correct |
84 |
Correct |
4 ms |
5844 KB |
Output is correct |
85 |
Correct |
4 ms |
5844 KB |
Output is correct |
86 |
Correct |
4 ms |
5792 KB |
Output is correct |
87 |
Correct |
5 ms |
5844 KB |
Output is correct |
88 |
Correct |
6 ms |
6228 KB |
Output is correct |
89 |
Correct |
6 ms |
6316 KB |
Output is correct |
90 |
Correct |
7 ms |
6356 KB |
Output is correct |
91 |
Correct |
5 ms |
6316 KB |
Output is correct |
92 |
Correct |
6 ms |
6356 KB |
Output is correct |
93 |
Correct |
3 ms |
5796 KB |
Output is correct |
94 |
Correct |
4 ms |
5844 KB |
Output is correct |
95 |
Correct |
4 ms |
5844 KB |
Output is correct |
96 |
Correct |
4 ms |
5844 KB |
Output is correct |
97 |
Correct |
4 ms |
5800 KB |
Output is correct |
98 |
Correct |
4 ms |
5796 KB |
Output is correct |
99 |
Correct |
6 ms |
6356 KB |
Output is correct |
100 |
Correct |
7 ms |
6356 KB |
Output is correct |
101 |
Correct |
7 ms |
6352 KB |
Output is correct |
102 |
Correct |
7 ms |
6356 KB |
Output is correct |
103 |
Correct |
6 ms |
6356 KB |
Output is correct |
104 |
Correct |
278 ms |
34004 KB |
Output is correct |
105 |
Correct |
276 ms |
34876 KB |
Output is correct |
106 |
Correct |
312 ms |
38260 KB |
Output is correct |
107 |
Correct |
278 ms |
36232 KB |
Output is correct |
108 |
Correct |
320 ms |
38280 KB |
Output is correct |
109 |
Correct |
297 ms |
37880 KB |
Output is correct |
110 |
Correct |
282 ms |
37404 KB |
Output is correct |
111 |
Correct |
200 ms |
35904 KB |
Output is correct |
112 |
Correct |
248 ms |
36172 KB |
Output is correct |
113 |
Correct |
275 ms |
35752 KB |
Output is correct |
114 |
Correct |
308 ms |
38104 KB |
Output is correct |
115 |
Correct |
258 ms |
38316 KB |
Output is correct |
116 |
Correct |
3 ms |
5716 KB |
Output is correct |
117 |
Correct |
117 ms |
39484 KB |
Output is correct |
118 |
Correct |
126 ms |
43236 KB |
Output is correct |
119 |
Correct |
6 ms |
6356 KB |
Output is correct |
120 |
Correct |
5 ms |
6352 KB |
Output is correct |
121 |
Correct |
6 ms |
6356 KB |
Output is correct |
122 |
Correct |
6 ms |
6356 KB |
Output is correct |
123 |
Correct |
7 ms |
6356 KB |
Output is correct |
124 |
Correct |
210 ms |
34992 KB |
Output is correct |
125 |
Correct |
4 ms |
5796 KB |
Output is correct |
126 |
Correct |
3 ms |
5716 KB |
Output is correct |
127 |
Correct |
3 ms |
5796 KB |
Output is correct |
128 |
Correct |
244 ms |
31948 KB |
Output is correct |
129 |
Correct |
214 ms |
29388 KB |
Output is correct |
130 |
Correct |
304 ms |
36268 KB |
Output is correct |
131 |
Correct |
363 ms |
38356 KB |
Output is correct |
132 |
Correct |
317 ms |
35756 KB |
Output is correct |
133 |
Correct |
326 ms |
36720 KB |
Output is correct |
134 |
Correct |
340 ms |
38036 KB |
Output is correct |
135 |
Correct |
282 ms |
34152 KB |
Output is correct |
136 |
Correct |
220 ms |
36648 KB |
Output is correct |
137 |
Correct |
327 ms |
37448 KB |
Output is correct |
138 |
Correct |
293 ms |
39036 KB |
Output is correct |
139 |
Correct |
336 ms |
38120 KB |
Output is correct |
140 |
Correct |
305 ms |
38328 KB |
Output is correct |
141 |
Correct |
81 ms |
28200 KB |
Output is correct |
142 |
Correct |
124 ms |
43128 KB |
Output is correct |
143 |
Correct |
6 ms |
6228 KB |
Output is correct |
144 |
Correct |
6 ms |
6376 KB |
Output is correct |
145 |
Correct |
8 ms |
6356 KB |
Output is correct |
146 |
Correct |
6 ms |
6356 KB |
Output is correct |
147 |
Correct |
6 ms |
6356 KB |
Output is correct |
148 |
Correct |
3 ms |
5792 KB |
Output is correct |
149 |
Correct |
4 ms |
5844 KB |
Output is correct |
150 |
Correct |
4 ms |
5796 KB |
Output is correct |
151 |
Correct |
4 ms |
5844 KB |
Output is correct |
152 |
Correct |
4 ms |
5844 KB |
Output is correct |
153 |
Correct |
132 ms |
24928 KB |
Output is correct |
154 |
Correct |
246 ms |
37944 KB |
Output is correct |
155 |
Correct |
293 ms |
35280 KB |
Output is correct |
156 |
Correct |
257 ms |
34688 KB |
Output is correct |
157 |
Correct |
308 ms |
38368 KB |
Output is correct |
158 |
Correct |
272 ms |
36284 KB |
Output is correct |
159 |
Correct |
364 ms |
38264 KB |
Output is correct |
160 |
Correct |
291 ms |
37912 KB |
Output is correct |
161 |
Correct |
278 ms |
37400 KB |
Output is correct |
162 |
Correct |
198 ms |
35880 KB |
Output is correct |
163 |
Correct |
266 ms |
36180 KB |
Output is correct |
164 |
Correct |
288 ms |
35736 KB |
Output is correct |
165 |
Correct |
287 ms |
38064 KB |
Output is correct |
166 |
Correct |
287 ms |
38288 KB |
Output is correct |
167 |
Correct |
4 ms |
5716 KB |
Output is correct |
168 |
Correct |
112 ms |
39528 KB |
Output is correct |
169 |
Correct |
137 ms |
43128 KB |
Output is correct |
170 |
Correct |
6 ms |
6356 KB |
Output is correct |
171 |
Correct |
6 ms |
6320 KB |
Output is correct |
172 |
Correct |
7 ms |
6356 KB |
Output is correct |
173 |
Correct |
6 ms |
6452 KB |
Output is correct |
174 |
Correct |
8 ms |
6356 KB |
Output is correct |
175 |
Correct |
189 ms |
34988 KB |
Output is correct |
176 |
Correct |
3 ms |
5716 KB |
Output is correct |
177 |
Correct |
310 ms |
36620 KB |
Output is correct |
178 |
Correct |
209 ms |
29872 KB |
Output is correct |
179 |
Correct |
323 ms |
38348 KB |
Output is correct |
180 |
Correct |
326 ms |
37028 KB |
Output is correct |
181 |
Correct |
345 ms |
39172 KB |
Output is correct |
182 |
Correct |
314 ms |
37928 KB |
Output is correct |
183 |
Correct |
303 ms |
37472 KB |
Output is correct |
184 |
Correct |
381 ms |
36492 KB |
Output is correct |
185 |
Correct |
351 ms |
37564 KB |
Output is correct |
186 |
Correct |
356 ms |
36500 KB |
Output is correct |
187 |
Correct |
284 ms |
39096 KB |
Output is correct |
188 |
Correct |
274 ms |
34928 KB |
Output is correct |
189 |
Correct |
264 ms |
35084 KB |
Output is correct |
190 |
Correct |
332 ms |
38884 KB |
Output is correct |
191 |
Correct |
299 ms |
38016 KB |
Output is correct |
192 |
Correct |
376 ms |
39196 KB |
Output is correct |
193 |
Correct |
430 ms |
39096 KB |
Output is correct |
194 |
Correct |
287 ms |
38960 KB |
Output is correct |
195 |
Correct |
109 ms |
37480 KB |
Output is correct |
196 |
Correct |
139 ms |
41548 KB |
Output is correct |
197 |
Correct |
138 ms |
43948 KB |
Output is correct |
198 |
Correct |
125 ms |
44004 KB |
Output is correct |
199 |
Correct |
5 ms |
6100 KB |
Output is correct |
200 |
Correct |
7 ms |
6356 KB |
Output is correct |
201 |
Correct |
8 ms |
6228 KB |
Output is correct |
202 |
Correct |
7 ms |
6448 KB |
Output is correct |
203 |
Correct |
7 ms |
6484 KB |
Output is correct |
204 |
Correct |
7 ms |
6440 KB |
Output is correct |
205 |
Correct |
6 ms |
6356 KB |
Output is correct |
206 |
Correct |
6 ms |
6356 KB |
Output is correct |
207 |
Correct |
6 ms |
6356 KB |
Output is correct |
208 |
Correct |
6 ms |
6484 KB |
Output is correct |
209 |
Correct |
5 ms |
6356 KB |
Output is correct |
210 |
Correct |
5 ms |
6580 KB |
Output is correct |
211 |
Correct |
5 ms |
6484 KB |
Output is correct |
212 |
Correct |
8 ms |
6356 KB |
Output is correct |
213 |
Correct |
7 ms |
6488 KB |
Output is correct |
214 |
Correct |
6 ms |
6484 KB |
Output is correct |
215 |
Correct |
3 ms |
5716 KB |
Output is correct |
216 |
Correct |
4 ms |
5792 KB |
Output is correct |
217 |
Correct |
3 ms |
5844 KB |
Output is correct |
218 |
Correct |
3 ms |
5844 KB |
Output is correct |
219 |
Correct |
3 ms |
5792 KB |
Output is correct |
220 |
Correct |
4 ms |
5844 KB |
Output is correct |
221 |
Correct |
3 ms |
5844 KB |
Output is correct |
222 |
Correct |
4 ms |
5844 KB |
Output is correct |
223 |
Correct |
4 ms |
5844 KB |
Output is correct |
224 |
Correct |
4 ms |
5844 KB |
Output is correct |
225 |
Correct |
4 ms |
5796 KB |
Output is correct |
226 |
Correct |
4 ms |
5844 KB |
Output is correct |
227 |
Correct |
4 ms |
5792 KB |
Output is correct |
228 |
Correct |
4 ms |
5844 KB |
Output is correct |
229 |
Correct |
258 ms |
31992 KB |
Output is correct |
230 |
Correct |
206 ms |
29524 KB |
Output is correct |
231 |
Correct |
278 ms |
36268 KB |
Output is correct |
232 |
Correct |
416 ms |
38280 KB |
Output is correct |
233 |
Correct |
323 ms |
35752 KB |
Output is correct |
234 |
Correct |
341 ms |
36728 KB |
Output is correct |
235 |
Correct |
351 ms |
37960 KB |
Output is correct |
236 |
Correct |
246 ms |
34020 KB |
Output is correct |
237 |
Correct |
233 ms |
36656 KB |
Output is correct |
238 |
Correct |
322 ms |
37448 KB |
Output is correct |
239 |
Correct |
313 ms |
38948 KB |
Output is correct |
240 |
Correct |
339 ms |
38104 KB |
Output is correct |
241 |
Correct |
307 ms |
38288 KB |
Output is correct |
242 |
Correct |
72 ms |
28220 KB |
Output is correct |
243 |
Correct |
125 ms |
43212 KB |
Output is correct |
244 |
Correct |
5 ms |
6228 KB |
Output is correct |
245 |
Correct |
6 ms |
6316 KB |
Output is correct |
246 |
Correct |
7 ms |
6356 KB |
Output is correct |
247 |
Correct |
6 ms |
6340 KB |
Output is correct |
248 |
Correct |
6 ms |
6356 KB |
Output is correct |
249 |
Correct |
3 ms |
5844 KB |
Output is correct |
250 |
Correct |
5 ms |
5844 KB |
Output is correct |
251 |
Correct |
4 ms |
5844 KB |
Output is correct |
252 |
Correct |
4 ms |
5796 KB |
Output is correct |
253 |
Correct |
5 ms |
5844 KB |
Output is correct |
254 |
Correct |
128 ms |
24996 KB |
Output is correct |
255 |
Correct |
241 ms |
37948 KB |
Output is correct |
256 |
Correct |
249 ms |
35416 KB |
Output is correct |
257 |
Correct |
303 ms |
38520 KB |
Output is correct |
258 |
Correct |
300 ms |
39032 KB |
Output is correct |
259 |
Correct |
252 ms |
39208 KB |
Output is correct |
260 |
Correct |
301 ms |
35332 KB |
Output is correct |
261 |
Correct |
294 ms |
34676 KB |
Output is correct |
262 |
Correct |
303 ms |
38252 KB |
Output is correct |
263 |
Correct |
282 ms |
36276 KB |
Output is correct |
264 |
Correct |
323 ms |
38284 KB |
Output is correct |
265 |
Correct |
270 ms |
37840 KB |
Output is correct |
266 |
Correct |
276 ms |
37400 KB |
Output is correct |
267 |
Correct |
243 ms |
35904 KB |
Output is correct |
268 |
Correct |
251 ms |
36108 KB |
Output is correct |
269 |
Correct |
320 ms |
35736 KB |
Output is correct |
270 |
Correct |
300 ms |
38092 KB |
Output is correct |
271 |
Correct |
284 ms |
38312 KB |
Output is correct |
272 |
Correct |
3 ms |
5796 KB |
Output is correct |
273 |
Correct |
106 ms |
39540 KB |
Output is correct |
274 |
Correct |
121 ms |
43172 KB |
Output is correct |
275 |
Correct |
8 ms |
6316 KB |
Output is correct |
276 |
Correct |
6 ms |
6448 KB |
Output is correct |
277 |
Correct |
6 ms |
6452 KB |
Output is correct |
278 |
Correct |
9 ms |
6444 KB |
Output is correct |
279 |
Correct |
6 ms |
6356 KB |
Output is correct |
280 |
Correct |
187 ms |
35020 KB |
Output is correct |