#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
constexpr ll INF2 = 4e18;
struct Edge{
int v, w, i;
Edge(){}
Edge(int _v, int _w, int _i): v(_v), w(_w), i(_i) {}
};
int n;
vector<pair<int, int>> adj[100100], dep;
list<Edge> G[100100];
int dcnt, in[100100], in2[100100], out[100100], pW[100100], deg[100100];
ll dp[100100][2];
int pt, k;
vector<int> V, on;
struct Node1{
ll sum, c, mn;
Node1(){}
Node1(ll x): sum(x), c(1), mn(x) {}
Node1(ll _s, ll _c, ll _mn): sum(_s), c(_c), mn(_mn) {}
Node1 operator + (const Node1 &N) const{
return Node1(sum + N.sum, c + N.c, min(mn, N.mn));
}
};
struct Seg1{
vector<Node1> tree;
int sz;
void update(int i, int l, int r, int p, ll x){
if (p<l || r<p) return;
if (l==r){
tree[i] = Node1(x);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, p, x); update(i<<1|1, m+1, r, p, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
int _search_below(int i, int l, int r, ll x){
if (tree[i].mn > x) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int ret = _search_below(i<<1|1, m+1, r, x);
if (ret==-1) return _search_below(i<<1, l, m, x);
return ret;
}
int _search_cnt(int i, int l, int r, int c){
if (l==r) return l;
int m = (l+r)>>1;
if (tree[i<<1].c < c) return _search_cnt(i<<1|1, m+1, r, c - tree[i<<1].c);
return _search_cnt(i<<1, l, m, c);
}
Node1 query(int i, int l, int r, int s, int e){
if (r<s || e<l) return Node1(0, 0, INF2);
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
}
void init(int _sz){sz = _sz; tree.clear(); tree.resize(sz*4 + 2, Node1(0, 0, INF2));}
void update(int p, ll x){
//printf(" update %d %lld\n", p, x);
update(1, 1, sz, p, x);
}
int count(ll x){
int idx = _search_below(1, 1, sz, x);
return query(1, 1, sz, 1, idx).c;
}
ll query(int c){
if (c<=0) return 0;
int idx = _search_cnt(1, 1, sz, c);
//printf(" query %d -> %d\n", c, idx);
return query(1, 1, sz, 1, idx).sum;
}
}tree[100100];
struct Seg2{
pair<int, int> tree[400400];
int sz;
void init(int n){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = dep[i-sz];
for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
pair<int, int> query(int l, int r){
++r;
pair<int, int> ret = {INF1, 0};
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret;
}
}rmq;
void dfs0(int s, int pa = 0, int paw = 0){
//printf("ok %d\n", s);
on.push_back(s);
pW[s] = paw;
in[s] = ++dcnt;
deg[s] = adj[s].size();
in2[s] = dep.size();
dep.emplace_back(dep[in2[pa]].first + 1, s);
sort(adj[s].begin(), adj[s].end());
for (auto &[w, v]:adj[s]) if (v!=pa){
G[s].emplace_back(v, w, G[s].size() + 1);
dfs0(v, s, w);
dep.emplace_back(dep[in2[pa]].first + 1, s);
}
tree[s].init(G[s].size());
out[s] = dcnt;
}
ll calc(int s, const vector<pair<ll, ll>> &C, int t){
int cnt = 0;
ll ret = 0;
for (int i=0;i<(int)C.size();i++){
auto [x, y] = C[i];
if (x > y || tree[s].count(y-x) + i + 1 <= t){
cnt++;
ret += y-x;
}
else break;
}
ret += tree[s].query(t-cnt);
//printf(" calc %d %d -> %d %lld\n", s, t, cnt, ret);
return ret;
}
bool cmp(const pair<ll, ll> &x, const pair<ll, ll> &y) {return x.second-x.first < y.second-y.first;}
void dfs(int s){
/*printf(" in %d\n", s);
if (s==1){
printf("G[1]:");
for (auto &[x, y, z]:G[s]) printf(" %d", x);
printf("\n");
}*/
auto iter = G[s].begin();
vector<pair<ll, ll>> C;
while(pt < (int)V.size() && in[V[pt]] <= out[s]){
while (in[V[pt]] > out[iter->v]){
tree[s].update(iter->i, iter->w);
iter = G[s].erase(iter);
}
//printf(" s = %d pointing %d\n", s, iter->v);
int v = V[pt];
pt++;
dfs(v);
if (iter->v == v){
C.emplace_back(dp[v][0], dp[v][1]);
}
else{
ll val = min(dp[v][0], dp[v][1]);
C.emplace_back(val, val + iter->w);
}
iter++;
}
while (iter!=G[s].end()){
tree[s].update(iter->i, iter->w);
iter = G[s].erase(iter);
}
/*if (s==1){
printf("G[1]:");
for (auto &[x, y, z]:G[s]) printf(" %d", x);
printf("\n");
}*/
dp[s][0] = 0, dp[s][1] = pW[s];
if (deg[s] <= k){
for (auto &[x, y]:C){
dp[s][0] += min(x, y);
dp[s][1] += min(x, y);
}
//printf(" s = %d -> %lld %lld\n", s, dp[s][0], dp[s][1]);
return;
}
for (auto &[x, y]:C){
dp[s][0] += x;
dp[s][1] += x;
}
sort(C.begin(), C.end(), cmp);
dp[s][0] += calc(s, C, deg[s]-k);
dp[s][1] += calc(s, C, deg[s]-k-1);
//printf(" s = %d -> %lld %lld\n", s, dp[s][0], dp[s][1]);
}
int lca(int x, int y){
assert(in2[x] < in2[y]);
auto [d, s] = rmq.query(in2[x], in2[y]);
return s;
}
bool cmp2(int x, int y){return in[x] < in[y];}
void getV(const vector<int> &on){
pt = 1;
V.clear();
V.push_back(1);
for (int i=0;i<(int)on.size();i++){
V.push_back(on[i]);
if (i) V.push_back(lca(on[i-1], on[i]));
}
sort(V.begin(), V.end(), cmp2);
V.erase(unique(V.begin(), V.end()), V.end());
/*printf("-----------------------------\n");
printf("k = %d\n", k);
for (auto &x:V) printf("%d ", x);
printf("\non: ");
for (auto &x:on) printf("%d(%d) ", x, in[x]);
printf("\n");*/
//printf("%d %d %d\n", in[14], dep[in[14]].first, dep[in[14]].second);
}
void getnxt(vector<int> &on, int k){
vector<int> nxt;
for (auto &x:on) if (deg[x] >= k) nxt.push_back(x);
swap(on, nxt);
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
dep.clear();
dep.emplace_back(0, 0);
for (int i=1;i<=n;i++){
adj[i].clear();
G[i].clear();
}
dcnt = 0;
vector<ll> ans(1);
for (int i=0;i<n-1;i++){
adj[U[i]+1].emplace_back(W[i], V[i]+1);
adj[V[i]+1].emplace_back(W[i], U[i]+1);
ans[0] += W[i];
}
dfs0(1);
rmq.init(dep.size());
for (k=1;k<=n-1;k++){
getV(on);
dfs(1);
ans.push_back(dp[1][0]);
getnxt(on, k+1);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
9 ms |
11924 KB |
Output is correct |
3 |
Correct |
9 ms |
12044 KB |
Output is correct |
4 |
Correct |
9 ms |
11936 KB |
Output is correct |
5 |
Correct |
5 ms |
11348 KB |
Output is correct |
6 |
Correct |
5 ms |
11348 KB |
Output is correct |
7 |
Correct |
7 ms |
11476 KB |
Output is correct |
8 |
Correct |
8 ms |
11860 KB |
Output is correct |
9 |
Correct |
8 ms |
11988 KB |
Output is correct |
10 |
Correct |
6 ms |
11348 KB |
Output is correct |
11 |
Correct |
6 ms |
11348 KB |
Output is correct |
12 |
Correct |
98 ms |
32972 KB |
Output is correct |
13 |
Correct |
176 ms |
47764 KB |
Output is correct |
14 |
Correct |
193 ms |
43960 KB |
Output is correct |
15 |
Correct |
193 ms |
47312 KB |
Output is correct |
16 |
Correct |
214 ms |
47676 KB |
Output is correct |
17 |
Correct |
164 ms |
47768 KB |
Output is correct |
18 |
Correct |
5 ms |
11220 KB |
Output is correct |
19 |
Correct |
149 ms |
44472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11220 KB |
Output is correct |
2 |
Correct |
101 ms |
54104 KB |
Output is correct |
3 |
Correct |
125 ms |
59336 KB |
Output is correct |
4 |
Correct |
124 ms |
62488 KB |
Output is correct |
5 |
Correct |
119 ms |
62480 KB |
Output is correct |
6 |
Correct |
7 ms |
12116 KB |
Output is correct |
7 |
Correct |
8 ms |
12244 KB |
Output is correct |
8 |
Correct |
7 ms |
12164 KB |
Output is correct |
9 |
Correct |
7 ms |
11348 KB |
Output is correct |
10 |
Correct |
7 ms |
11348 KB |
Output is correct |
11 |
Correct |
6 ms |
11348 KB |
Output is correct |
12 |
Correct |
72 ms |
41796 KB |
Output is correct |
13 |
Correct |
115 ms |
62520 KB |
Output is correct |
14 |
Correct |
6 ms |
11220 KB |
Output is correct |
15 |
Correct |
103 ms |
57628 KB |
Output is correct |
16 |
Correct |
114 ms |
62512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
6 ms |
11220 KB |
Output is correct |
4 |
Correct |
6 ms |
11348 KB |
Output is correct |
5 |
Correct |
6 ms |
11304 KB |
Output is correct |
6 |
Correct |
6 ms |
11348 KB |
Output is correct |
7 |
Correct |
7 ms |
11348 KB |
Output is correct |
8 |
Correct |
6 ms |
11276 KB |
Output is correct |
9 |
Correct |
6 ms |
11308 KB |
Output is correct |
10 |
Correct |
8 ms |
11276 KB |
Output is correct |
11 |
Correct |
7 ms |
11348 KB |
Output is correct |
12 |
Correct |
6 ms |
11348 KB |
Output is correct |
13 |
Correct |
7 ms |
11300 KB |
Output is correct |
14 |
Correct |
6 ms |
11348 KB |
Output is correct |
15 |
Correct |
7 ms |
11348 KB |
Output is correct |
16 |
Correct |
6 ms |
11276 KB |
Output is correct |
17 |
Correct |
7 ms |
11348 KB |
Output is correct |
18 |
Correct |
6 ms |
11348 KB |
Output is correct |
19 |
Correct |
7 ms |
11332 KB |
Output is correct |
20 |
Correct |
6 ms |
11348 KB |
Output is correct |
21 |
Correct |
6 ms |
11220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
6 ms |
11220 KB |
Output is correct |
4 |
Correct |
6 ms |
11348 KB |
Output is correct |
5 |
Correct |
6 ms |
11304 KB |
Output is correct |
6 |
Correct |
6 ms |
11348 KB |
Output is correct |
7 |
Correct |
7 ms |
11348 KB |
Output is correct |
8 |
Correct |
6 ms |
11276 KB |
Output is correct |
9 |
Correct |
6 ms |
11308 KB |
Output is correct |
10 |
Correct |
8 ms |
11276 KB |
Output is correct |
11 |
Correct |
7 ms |
11348 KB |
Output is correct |
12 |
Correct |
6 ms |
11348 KB |
Output is correct |
13 |
Correct |
7 ms |
11300 KB |
Output is correct |
14 |
Correct |
6 ms |
11348 KB |
Output is correct |
15 |
Correct |
7 ms |
11348 KB |
Output is correct |
16 |
Correct |
6 ms |
11276 KB |
Output is correct |
17 |
Correct |
7 ms |
11348 KB |
Output is correct |
18 |
Correct |
6 ms |
11348 KB |
Output is correct |
19 |
Correct |
7 ms |
11332 KB |
Output is correct |
20 |
Correct |
6 ms |
11348 KB |
Output is correct |
21 |
Correct |
6 ms |
11220 KB |
Output is correct |
22 |
Correct |
6 ms |
11304 KB |
Output is correct |
23 |
Correct |
9 ms |
11732 KB |
Output is correct |
24 |
Correct |
9 ms |
11988 KB |
Output is correct |
25 |
Correct |
9 ms |
11932 KB |
Output is correct |
26 |
Correct |
9 ms |
11988 KB |
Output is correct |
27 |
Correct |
10 ms |
11988 KB |
Output is correct |
28 |
Correct |
9 ms |
11976 KB |
Output is correct |
29 |
Correct |
8 ms |
11924 KB |
Output is correct |
30 |
Correct |
8 ms |
11936 KB |
Output is correct |
31 |
Correct |
9 ms |
11936 KB |
Output is correct |
32 |
Correct |
9 ms |
11956 KB |
Output is correct |
33 |
Correct |
7 ms |
12124 KB |
Output is correct |
34 |
Correct |
8 ms |
12324 KB |
Output is correct |
35 |
Correct |
9 ms |
12196 KB |
Output is correct |
36 |
Correct |
10 ms |
12000 KB |
Output is correct |
37 |
Correct |
9 ms |
12000 KB |
Output is correct |
38 |
Correct |
12 ms |
12040 KB |
Output is correct |
39 |
Correct |
6 ms |
11312 KB |
Output is correct |
40 |
Correct |
7 ms |
11288 KB |
Output is correct |
41 |
Correct |
7 ms |
11292 KB |
Output is correct |
42 |
Correct |
6 ms |
11284 KB |
Output is correct |
43 |
Correct |
6 ms |
11360 KB |
Output is correct |
44 |
Correct |
6 ms |
11360 KB |
Output is correct |
45 |
Correct |
6 ms |
11284 KB |
Output is correct |
46 |
Correct |
6 ms |
11284 KB |
Output is correct |
47 |
Correct |
6 ms |
11360 KB |
Output is correct |
48 |
Correct |
6 ms |
11412 KB |
Output is correct |
49 |
Correct |
6 ms |
11360 KB |
Output is correct |
50 |
Correct |
6 ms |
11284 KB |
Output is correct |
51 |
Correct |
6 ms |
11360 KB |
Output is correct |
52 |
Correct |
8 ms |
11292 KB |
Output is correct |
53 |
Correct |
8 ms |
11860 KB |
Output is correct |
54 |
Correct |
9 ms |
11928 KB |
Output is correct |
55 |
Correct |
8 ms |
11988 KB |
Output is correct |
56 |
Correct |
8 ms |
11860 KB |
Output is correct |
57 |
Correct |
8 ms |
12052 KB |
Output is correct |
58 |
Correct |
6 ms |
11344 KB |
Output is correct |
59 |
Correct |
6 ms |
11280 KB |
Output is correct |
60 |
Correct |
6 ms |
11276 KB |
Output is correct |
61 |
Correct |
6 ms |
11348 KB |
Output is correct |
62 |
Correct |
6 ms |
11348 KB |
Output is correct |
63 |
Correct |
6 ms |
11276 KB |
Output is correct |
64 |
Correct |
9 ms |
11988 KB |
Output is correct |
65 |
Correct |
10 ms |
11928 KB |
Output is correct |
66 |
Correct |
9 ms |
11988 KB |
Output is correct |
67 |
Correct |
9 ms |
11988 KB |
Output is correct |
68 |
Correct |
9 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
44840 KB |
Output is correct |
2 |
Correct |
213 ms |
45516 KB |
Output is correct |
3 |
Correct |
222 ms |
47852 KB |
Output is correct |
4 |
Correct |
236 ms |
47268 KB |
Output is correct |
5 |
Correct |
237 ms |
47892 KB |
Output is correct |
6 |
Correct |
197 ms |
48368 KB |
Output is correct |
7 |
Correct |
261 ms |
47472 KB |
Output is correct |
8 |
Correct |
155 ms |
46388 KB |
Output is correct |
9 |
Correct |
207 ms |
51360 KB |
Output is correct |
10 |
Correct |
251 ms |
46404 KB |
Output is correct |
11 |
Correct |
228 ms |
47752 KB |
Output is correct |
12 |
Correct |
179 ms |
48316 KB |
Output is correct |
13 |
Correct |
6 ms |
11220 KB |
Output is correct |
14 |
Correct |
106 ms |
58768 KB |
Output is correct |
15 |
Correct |
148 ms |
63868 KB |
Output is correct |
16 |
Correct |
11 ms |
11956 KB |
Output is correct |
17 |
Correct |
9 ms |
11988 KB |
Output is correct |
18 |
Correct |
9 ms |
11988 KB |
Output is correct |
19 |
Correct |
10 ms |
11988 KB |
Output is correct |
20 |
Correct |
9 ms |
11988 KB |
Output is correct |
21 |
Correct |
146 ms |
45344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
44840 KB |
Output is correct |
2 |
Correct |
213 ms |
45516 KB |
Output is correct |
3 |
Correct |
222 ms |
47852 KB |
Output is correct |
4 |
Correct |
236 ms |
47268 KB |
Output is correct |
5 |
Correct |
237 ms |
47892 KB |
Output is correct |
6 |
Correct |
197 ms |
48368 KB |
Output is correct |
7 |
Correct |
261 ms |
47472 KB |
Output is correct |
8 |
Correct |
155 ms |
46388 KB |
Output is correct |
9 |
Correct |
207 ms |
51360 KB |
Output is correct |
10 |
Correct |
251 ms |
46404 KB |
Output is correct |
11 |
Correct |
228 ms |
47752 KB |
Output is correct |
12 |
Correct |
179 ms |
48316 KB |
Output is correct |
13 |
Correct |
6 ms |
11220 KB |
Output is correct |
14 |
Correct |
106 ms |
58768 KB |
Output is correct |
15 |
Correct |
148 ms |
63868 KB |
Output is correct |
16 |
Correct |
11 ms |
11956 KB |
Output is correct |
17 |
Correct |
9 ms |
11988 KB |
Output is correct |
18 |
Correct |
9 ms |
11988 KB |
Output is correct |
19 |
Correct |
10 ms |
11988 KB |
Output is correct |
20 |
Correct |
9 ms |
11988 KB |
Output is correct |
21 |
Correct |
146 ms |
45344 KB |
Output is correct |
22 |
Correct |
6 ms |
11204 KB |
Output is correct |
23 |
Correct |
5 ms |
11188 KB |
Output is correct |
24 |
Correct |
6 ms |
11220 KB |
Output is correct |
25 |
Correct |
214 ms |
42340 KB |
Output is correct |
26 |
Correct |
175 ms |
39556 KB |
Output is correct |
27 |
Correct |
251 ms |
47400 KB |
Output is correct |
28 |
Correct |
242 ms |
47876 KB |
Output is correct |
29 |
Correct |
195 ms |
45132 KB |
Output is correct |
30 |
Correct |
199 ms |
46940 KB |
Output is correct |
31 |
Correct |
190 ms |
48000 KB |
Output is correct |
32 |
Correct |
248 ms |
44420 KB |
Output is correct |
33 |
Correct |
173 ms |
47168 KB |
Output is correct |
34 |
Correct |
237 ms |
47420 KB |
Output is correct |
35 |
Correct |
234 ms |
53624 KB |
Output is correct |
36 |
Correct |
253 ms |
47768 KB |
Output is correct |
37 |
Correct |
182 ms |
48276 KB |
Output is correct |
38 |
Correct |
73 ms |
42668 KB |
Output is correct |
39 |
Correct |
118 ms |
63804 KB |
Output is correct |
40 |
Correct |
8 ms |
11860 KB |
Output is correct |
41 |
Correct |
10 ms |
11924 KB |
Output is correct |
42 |
Correct |
8 ms |
11988 KB |
Output is correct |
43 |
Correct |
8 ms |
11928 KB |
Output is correct |
44 |
Correct |
8 ms |
11988 KB |
Output is correct |
45 |
Correct |
6 ms |
11220 KB |
Output is correct |
46 |
Correct |
6 ms |
11348 KB |
Output is correct |
47 |
Correct |
6 ms |
11348 KB |
Output is correct |
48 |
Correct |
6 ms |
11276 KB |
Output is correct |
49 |
Correct |
6 ms |
11348 KB |
Output is correct |
50 |
Correct |
106 ms |
33536 KB |
Output is correct |
51 |
Correct |
171 ms |
48740 KB |
Output is correct |
52 |
Correct |
193 ms |
46172 KB |
Output is correct |
53 |
Correct |
210 ms |
45516 KB |
Output is correct |
54 |
Correct |
230 ms |
47868 KB |
Output is correct |
55 |
Correct |
216 ms |
47228 KB |
Output is correct |
56 |
Correct |
215 ms |
48008 KB |
Output is correct |
57 |
Correct |
189 ms |
48344 KB |
Output is correct |
58 |
Correct |
241 ms |
47436 KB |
Output is correct |
59 |
Correct |
155 ms |
46352 KB |
Output is correct |
60 |
Correct |
190 ms |
51352 KB |
Output is correct |
61 |
Correct |
255 ms |
46320 KB |
Output is correct |
62 |
Correct |
229 ms |
47856 KB |
Output is correct |
63 |
Correct |
168 ms |
48316 KB |
Output is correct |
64 |
Correct |
5 ms |
11220 KB |
Output is correct |
65 |
Correct |
107 ms |
58764 KB |
Output is correct |
66 |
Correct |
117 ms |
63752 KB |
Output is correct |
67 |
Correct |
8 ms |
11988 KB |
Output is correct |
68 |
Correct |
8 ms |
12008 KB |
Output is correct |
69 |
Correct |
8 ms |
11924 KB |
Output is correct |
70 |
Correct |
9 ms |
11928 KB |
Output is correct |
71 |
Correct |
8 ms |
11988 KB |
Output is correct |
72 |
Correct |
141 ms |
45400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
9 ms |
11924 KB |
Output is correct |
3 |
Correct |
9 ms |
12044 KB |
Output is correct |
4 |
Correct |
9 ms |
11936 KB |
Output is correct |
5 |
Correct |
5 ms |
11348 KB |
Output is correct |
6 |
Correct |
5 ms |
11348 KB |
Output is correct |
7 |
Correct |
7 ms |
11476 KB |
Output is correct |
8 |
Correct |
8 ms |
11860 KB |
Output is correct |
9 |
Correct |
8 ms |
11988 KB |
Output is correct |
10 |
Correct |
6 ms |
11348 KB |
Output is correct |
11 |
Correct |
6 ms |
11348 KB |
Output is correct |
12 |
Correct |
98 ms |
32972 KB |
Output is correct |
13 |
Correct |
176 ms |
47764 KB |
Output is correct |
14 |
Correct |
193 ms |
43960 KB |
Output is correct |
15 |
Correct |
193 ms |
47312 KB |
Output is correct |
16 |
Correct |
214 ms |
47676 KB |
Output is correct |
17 |
Correct |
164 ms |
47768 KB |
Output is correct |
18 |
Correct |
5 ms |
11220 KB |
Output is correct |
19 |
Correct |
149 ms |
44472 KB |
Output is correct |
20 |
Correct |
5 ms |
11220 KB |
Output is correct |
21 |
Correct |
101 ms |
54104 KB |
Output is correct |
22 |
Correct |
125 ms |
59336 KB |
Output is correct |
23 |
Correct |
124 ms |
62488 KB |
Output is correct |
24 |
Correct |
119 ms |
62480 KB |
Output is correct |
25 |
Correct |
7 ms |
12116 KB |
Output is correct |
26 |
Correct |
8 ms |
12244 KB |
Output is correct |
27 |
Correct |
7 ms |
12164 KB |
Output is correct |
28 |
Correct |
7 ms |
11348 KB |
Output is correct |
29 |
Correct |
7 ms |
11348 KB |
Output is correct |
30 |
Correct |
6 ms |
11348 KB |
Output is correct |
31 |
Correct |
72 ms |
41796 KB |
Output is correct |
32 |
Correct |
115 ms |
62520 KB |
Output is correct |
33 |
Correct |
6 ms |
11220 KB |
Output is correct |
34 |
Correct |
103 ms |
57628 KB |
Output is correct |
35 |
Correct |
114 ms |
62512 KB |
Output is correct |
36 |
Correct |
6 ms |
11220 KB |
Output is correct |
37 |
Correct |
6 ms |
11220 KB |
Output is correct |
38 |
Correct |
6 ms |
11220 KB |
Output is correct |
39 |
Correct |
6 ms |
11348 KB |
Output is correct |
40 |
Correct |
6 ms |
11304 KB |
Output is correct |
41 |
Correct |
6 ms |
11348 KB |
Output is correct |
42 |
Correct |
7 ms |
11348 KB |
Output is correct |
43 |
Correct |
6 ms |
11276 KB |
Output is correct |
44 |
Correct |
6 ms |
11308 KB |
Output is correct |
45 |
Correct |
8 ms |
11276 KB |
Output is correct |
46 |
Correct |
7 ms |
11348 KB |
Output is correct |
47 |
Correct |
6 ms |
11348 KB |
Output is correct |
48 |
Correct |
7 ms |
11300 KB |
Output is correct |
49 |
Correct |
6 ms |
11348 KB |
Output is correct |
50 |
Correct |
7 ms |
11348 KB |
Output is correct |
51 |
Correct |
6 ms |
11276 KB |
Output is correct |
52 |
Correct |
7 ms |
11348 KB |
Output is correct |
53 |
Correct |
6 ms |
11348 KB |
Output is correct |
54 |
Correct |
7 ms |
11332 KB |
Output is correct |
55 |
Correct |
6 ms |
11348 KB |
Output is correct |
56 |
Correct |
6 ms |
11220 KB |
Output is correct |
57 |
Correct |
6 ms |
11304 KB |
Output is correct |
58 |
Correct |
9 ms |
11732 KB |
Output is correct |
59 |
Correct |
9 ms |
11988 KB |
Output is correct |
60 |
Correct |
9 ms |
11932 KB |
Output is correct |
61 |
Correct |
9 ms |
11988 KB |
Output is correct |
62 |
Correct |
10 ms |
11988 KB |
Output is correct |
63 |
Correct |
9 ms |
11976 KB |
Output is correct |
64 |
Correct |
8 ms |
11924 KB |
Output is correct |
65 |
Correct |
8 ms |
11936 KB |
Output is correct |
66 |
Correct |
9 ms |
11936 KB |
Output is correct |
67 |
Correct |
9 ms |
11956 KB |
Output is correct |
68 |
Correct |
7 ms |
12124 KB |
Output is correct |
69 |
Correct |
8 ms |
12324 KB |
Output is correct |
70 |
Correct |
9 ms |
12196 KB |
Output is correct |
71 |
Correct |
10 ms |
12000 KB |
Output is correct |
72 |
Correct |
9 ms |
12000 KB |
Output is correct |
73 |
Correct |
12 ms |
12040 KB |
Output is correct |
74 |
Correct |
6 ms |
11312 KB |
Output is correct |
75 |
Correct |
7 ms |
11288 KB |
Output is correct |
76 |
Correct |
7 ms |
11292 KB |
Output is correct |
77 |
Correct |
6 ms |
11284 KB |
Output is correct |
78 |
Correct |
6 ms |
11360 KB |
Output is correct |
79 |
Correct |
6 ms |
11360 KB |
Output is correct |
80 |
Correct |
6 ms |
11284 KB |
Output is correct |
81 |
Correct |
6 ms |
11284 KB |
Output is correct |
82 |
Correct |
6 ms |
11360 KB |
Output is correct |
83 |
Correct |
6 ms |
11412 KB |
Output is correct |
84 |
Correct |
6 ms |
11360 KB |
Output is correct |
85 |
Correct |
6 ms |
11284 KB |
Output is correct |
86 |
Correct |
6 ms |
11360 KB |
Output is correct |
87 |
Correct |
8 ms |
11292 KB |
Output is correct |
88 |
Correct |
8 ms |
11860 KB |
Output is correct |
89 |
Correct |
9 ms |
11928 KB |
Output is correct |
90 |
Correct |
8 ms |
11988 KB |
Output is correct |
91 |
Correct |
8 ms |
11860 KB |
Output is correct |
92 |
Correct |
8 ms |
12052 KB |
Output is correct |
93 |
Correct |
6 ms |
11344 KB |
Output is correct |
94 |
Correct |
6 ms |
11280 KB |
Output is correct |
95 |
Correct |
6 ms |
11276 KB |
Output is correct |
96 |
Correct |
6 ms |
11348 KB |
Output is correct |
97 |
Correct |
6 ms |
11348 KB |
Output is correct |
98 |
Correct |
6 ms |
11276 KB |
Output is correct |
99 |
Correct |
9 ms |
11988 KB |
Output is correct |
100 |
Correct |
10 ms |
11928 KB |
Output is correct |
101 |
Correct |
9 ms |
11988 KB |
Output is correct |
102 |
Correct |
9 ms |
11988 KB |
Output is correct |
103 |
Correct |
9 ms |
11988 KB |
Output is correct |
104 |
Correct |
238 ms |
44840 KB |
Output is correct |
105 |
Correct |
213 ms |
45516 KB |
Output is correct |
106 |
Correct |
222 ms |
47852 KB |
Output is correct |
107 |
Correct |
236 ms |
47268 KB |
Output is correct |
108 |
Correct |
237 ms |
47892 KB |
Output is correct |
109 |
Correct |
197 ms |
48368 KB |
Output is correct |
110 |
Correct |
261 ms |
47472 KB |
Output is correct |
111 |
Correct |
155 ms |
46388 KB |
Output is correct |
112 |
Correct |
207 ms |
51360 KB |
Output is correct |
113 |
Correct |
251 ms |
46404 KB |
Output is correct |
114 |
Correct |
228 ms |
47752 KB |
Output is correct |
115 |
Correct |
179 ms |
48316 KB |
Output is correct |
116 |
Correct |
6 ms |
11220 KB |
Output is correct |
117 |
Correct |
106 ms |
58768 KB |
Output is correct |
118 |
Correct |
148 ms |
63868 KB |
Output is correct |
119 |
Correct |
11 ms |
11956 KB |
Output is correct |
120 |
Correct |
9 ms |
11988 KB |
Output is correct |
121 |
Correct |
9 ms |
11988 KB |
Output is correct |
122 |
Correct |
10 ms |
11988 KB |
Output is correct |
123 |
Correct |
9 ms |
11988 KB |
Output is correct |
124 |
Correct |
146 ms |
45344 KB |
Output is correct |
125 |
Correct |
6 ms |
11204 KB |
Output is correct |
126 |
Correct |
5 ms |
11188 KB |
Output is correct |
127 |
Correct |
6 ms |
11220 KB |
Output is correct |
128 |
Correct |
214 ms |
42340 KB |
Output is correct |
129 |
Correct |
175 ms |
39556 KB |
Output is correct |
130 |
Correct |
251 ms |
47400 KB |
Output is correct |
131 |
Correct |
242 ms |
47876 KB |
Output is correct |
132 |
Correct |
195 ms |
45132 KB |
Output is correct |
133 |
Correct |
199 ms |
46940 KB |
Output is correct |
134 |
Correct |
190 ms |
48000 KB |
Output is correct |
135 |
Correct |
248 ms |
44420 KB |
Output is correct |
136 |
Correct |
173 ms |
47168 KB |
Output is correct |
137 |
Correct |
237 ms |
47420 KB |
Output is correct |
138 |
Correct |
234 ms |
53624 KB |
Output is correct |
139 |
Correct |
253 ms |
47768 KB |
Output is correct |
140 |
Correct |
182 ms |
48276 KB |
Output is correct |
141 |
Correct |
73 ms |
42668 KB |
Output is correct |
142 |
Correct |
118 ms |
63804 KB |
Output is correct |
143 |
Correct |
8 ms |
11860 KB |
Output is correct |
144 |
Correct |
10 ms |
11924 KB |
Output is correct |
145 |
Correct |
8 ms |
11988 KB |
Output is correct |
146 |
Correct |
8 ms |
11928 KB |
Output is correct |
147 |
Correct |
8 ms |
11988 KB |
Output is correct |
148 |
Correct |
6 ms |
11220 KB |
Output is correct |
149 |
Correct |
6 ms |
11348 KB |
Output is correct |
150 |
Correct |
6 ms |
11348 KB |
Output is correct |
151 |
Correct |
6 ms |
11276 KB |
Output is correct |
152 |
Correct |
6 ms |
11348 KB |
Output is correct |
153 |
Correct |
106 ms |
33536 KB |
Output is correct |
154 |
Correct |
171 ms |
48740 KB |
Output is correct |
155 |
Correct |
193 ms |
46172 KB |
Output is correct |
156 |
Correct |
210 ms |
45516 KB |
Output is correct |
157 |
Correct |
230 ms |
47868 KB |
Output is correct |
158 |
Correct |
216 ms |
47228 KB |
Output is correct |
159 |
Correct |
215 ms |
48008 KB |
Output is correct |
160 |
Correct |
189 ms |
48344 KB |
Output is correct |
161 |
Correct |
241 ms |
47436 KB |
Output is correct |
162 |
Correct |
155 ms |
46352 KB |
Output is correct |
163 |
Correct |
190 ms |
51352 KB |
Output is correct |
164 |
Correct |
255 ms |
46320 KB |
Output is correct |
165 |
Correct |
229 ms |
47856 KB |
Output is correct |
166 |
Correct |
168 ms |
48316 KB |
Output is correct |
167 |
Correct |
5 ms |
11220 KB |
Output is correct |
168 |
Correct |
107 ms |
58764 KB |
Output is correct |
169 |
Correct |
117 ms |
63752 KB |
Output is correct |
170 |
Correct |
8 ms |
11988 KB |
Output is correct |
171 |
Correct |
8 ms |
12008 KB |
Output is correct |
172 |
Correct |
8 ms |
11924 KB |
Output is correct |
173 |
Correct |
9 ms |
11928 KB |
Output is correct |
174 |
Correct |
8 ms |
11988 KB |
Output is correct |
175 |
Correct |
141 ms |
45400 KB |
Output is correct |
176 |
Correct |
5 ms |
11272 KB |
Output is correct |
177 |
Correct |
238 ms |
47612 KB |
Output is correct |
178 |
Correct |
156 ms |
40020 KB |
Output is correct |
179 |
Correct |
209 ms |
47900 KB |
Output is correct |
180 |
Correct |
213 ms |
46520 KB |
Output is correct |
181 |
Correct |
221 ms |
48888 KB |
Output is correct |
182 |
Correct |
191 ms |
48392 KB |
Output is correct |
183 |
Correct |
198 ms |
47548 KB |
Output is correct |
184 |
Correct |
197 ms |
47228 KB |
Output is correct |
185 |
Correct |
185 ms |
47832 KB |
Output is correct |
186 |
Correct |
184 ms |
46292 KB |
Output is correct |
187 |
Correct |
211 ms |
49532 KB |
Output is correct |
188 |
Correct |
213 ms |
45648 KB |
Output is correct |
189 |
Correct |
208 ms |
45444 KB |
Output is correct |
190 |
Correct |
240 ms |
48444 KB |
Output is correct |
191 |
Correct |
196 ms |
47732 KB |
Output is correct |
192 |
Correct |
196 ms |
49032 KB |
Output is correct |
193 |
Correct |
225 ms |
49048 KB |
Output is correct |
194 |
Correct |
239 ms |
48612 KB |
Output is correct |
195 |
Correct |
100 ms |
55868 KB |
Output is correct |
196 |
Correct |
125 ms |
61320 KB |
Output is correct |
197 |
Correct |
121 ms |
64636 KB |
Output is correct |
198 |
Correct |
122 ms |
64640 KB |
Output is correct |
199 |
Correct |
7 ms |
11656 KB |
Output is correct |
200 |
Correct |
9 ms |
11964 KB |
Output is correct |
201 |
Correct |
8 ms |
11928 KB |
Output is correct |
202 |
Correct |
8 ms |
11924 KB |
Output is correct |
203 |
Correct |
10 ms |
11988 KB |
Output is correct |
204 |
Correct |
8 ms |
12000 KB |
Output is correct |
205 |
Correct |
8 ms |
11860 KB |
Output is correct |
206 |
Correct |
9 ms |
11988 KB |
Output is correct |
207 |
Correct |
8 ms |
12024 KB |
Output is correct |
208 |
Correct |
8 ms |
11976 KB |
Output is correct |
209 |
Correct |
7 ms |
12116 KB |
Output is correct |
210 |
Correct |
8 ms |
12244 KB |
Output is correct |
211 |
Correct |
7 ms |
12244 KB |
Output is correct |
212 |
Correct |
8 ms |
11988 KB |
Output is correct |
213 |
Correct |
8 ms |
12060 KB |
Output is correct |
214 |
Correct |
8 ms |
11988 KB |
Output is correct |
215 |
Correct |
6 ms |
11232 KB |
Output is correct |
216 |
Correct |
5 ms |
11220 KB |
Output is correct |
217 |
Correct |
6 ms |
11348 KB |
Output is correct |
218 |
Correct |
6 ms |
11272 KB |
Output is correct |
219 |
Correct |
6 ms |
11272 KB |
Output is correct |
220 |
Correct |
6 ms |
11348 KB |
Output is correct |
221 |
Correct |
6 ms |
11348 KB |
Output is correct |
222 |
Correct |
6 ms |
11276 KB |
Output is correct |
223 |
Correct |
6 ms |
11348 KB |
Output is correct |
224 |
Correct |
6 ms |
11276 KB |
Output is correct |
225 |
Correct |
6 ms |
11328 KB |
Output is correct |
226 |
Correct |
6 ms |
11348 KB |
Output is correct |
227 |
Correct |
6 ms |
11264 KB |
Output is correct |
228 |
Correct |
6 ms |
11272 KB |
Output is correct |
229 |
Correct |
182 ms |
42364 KB |
Output is correct |
230 |
Correct |
175 ms |
39556 KB |
Output is correct |
231 |
Correct |
238 ms |
47372 KB |
Output is correct |
232 |
Correct |
243 ms |
47884 KB |
Output is correct |
233 |
Correct |
197 ms |
45224 KB |
Output is correct |
234 |
Correct |
193 ms |
47020 KB |
Output is correct |
235 |
Correct |
194 ms |
47984 KB |
Output is correct |
236 |
Correct |
245 ms |
44372 KB |
Output is correct |
237 |
Correct |
167 ms |
47120 KB |
Output is correct |
238 |
Correct |
239 ms |
47420 KB |
Output is correct |
239 |
Correct |
233 ms |
53560 KB |
Output is correct |
240 |
Correct |
241 ms |
47676 KB |
Output is correct |
241 |
Correct |
186 ms |
48320 KB |
Output is correct |
242 |
Correct |
74 ms |
42560 KB |
Output is correct |
243 |
Correct |
121 ms |
63804 KB |
Output is correct |
244 |
Correct |
8 ms |
11832 KB |
Output is correct |
245 |
Correct |
8 ms |
11988 KB |
Output is correct |
246 |
Correct |
9 ms |
11956 KB |
Output is correct |
247 |
Correct |
8 ms |
11860 KB |
Output is correct |
248 |
Correct |
8 ms |
11988 KB |
Output is correct |
249 |
Correct |
6 ms |
11244 KB |
Output is correct |
250 |
Correct |
6 ms |
11268 KB |
Output is correct |
251 |
Correct |
6 ms |
11276 KB |
Output is correct |
252 |
Correct |
6 ms |
11348 KB |
Output is correct |
253 |
Correct |
6 ms |
11348 KB |
Output is correct |
254 |
Correct |
97 ms |
33600 KB |
Output is correct |
255 |
Correct |
168 ms |
48760 KB |
Output is correct |
256 |
Correct |
173 ms |
45436 KB |
Output is correct |
257 |
Correct |
197 ms |
49016 KB |
Output is correct |
258 |
Correct |
199 ms |
49468 KB |
Output is correct |
259 |
Correct |
162 ms |
49596 KB |
Output is correct |
260 |
Correct |
202 ms |
46112 KB |
Output is correct |
261 |
Correct |
204 ms |
45556 KB |
Output is correct |
262 |
Correct |
217 ms |
47932 KB |
Output is correct |
263 |
Correct |
219 ms |
47232 KB |
Output is correct |
264 |
Correct |
205 ms |
47876 KB |
Output is correct |
265 |
Correct |
183 ms |
48324 KB |
Output is correct |
266 |
Correct |
246 ms |
47364 KB |
Output is correct |
267 |
Correct |
149 ms |
46396 KB |
Output is correct |
268 |
Correct |
188 ms |
51388 KB |
Output is correct |
269 |
Correct |
257 ms |
46328 KB |
Output is correct |
270 |
Correct |
233 ms |
47868 KB |
Output is correct |
271 |
Correct |
161 ms |
48268 KB |
Output is correct |
272 |
Correct |
6 ms |
11220 KB |
Output is correct |
273 |
Correct |
109 ms |
58756 KB |
Output is correct |
274 |
Correct |
122 ms |
64004 KB |
Output is correct |
275 |
Correct |
9 ms |
11988 KB |
Output is correct |
276 |
Correct |
8 ms |
11932 KB |
Output is correct |
277 |
Correct |
8 ms |
11964 KB |
Output is correct |
278 |
Correct |
9 ms |
11908 KB |
Output is correct |
279 |
Correct |
8 ms |
11928 KB |
Output is correct |
280 |
Correct |
140 ms |
45344 KB |
Output is correct |