#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,d[100001],p[1000001],level[1000001],de[100001];
ll dp[100001][2],w[100001],sum,c[100001];
vector<int> deg;
vector<pii> adj[100001];
vector<ll> ans;
bool comp(pii a, pii b) {return a.second<b.second;}
bool comp2(int a, int b) {return level[a]>level[b];}
bool comp3(int a, int b) {return d[a]>d[b];}
struct node {
int cnt,prior;
ll val,sum;
node *l, *r;
node(ll v) : cnt(1), val(v), sum(v), prior(rand()), l(NULL), r(NULL) {}
};
typedef node* pnode;
pnode tr[100001];
void upd(pnode t) {
if (t) {
t->cnt=1;
t->sum=t->val;
if (t->l) {
t->cnt+=t->l->cnt;
t->sum+=t->l->sum;
}
if (t->r) {
t->cnt+=t->r->cnt;
t->sum+=t->r->sum;
}
}
}
int get_cnt(pnode t) {
if (!t) return 0;
else return t->cnt;
}
void split1(pnode t, pnode &l, pnode &r, int v) { //split by cnt
if (t==NULL) l=r=NULL;
else if (get_cnt(t->l)>=v) split1(t->l,l,t->l,v), r=t;
else split1(t->r,t->r,r,v-get_cnt(t->l)-1), l=t;
upd(t);
}
void split2(pnode t, pnode &l, pnode &r, int v) { //split by val
if (t==NULL) l=r=NULL;
else if (t->val>=v) split2(t->l,l,t->l,v), r=t;
else split2(t->r,t->r,r,v), l=t;
upd(t);
}
void merge(pnode l, pnode r, pnode &t) {
if (!l) t=r;
else if (!r) t=l;
else if (l->prior>=r->prior) merge(l->r,r,l->r), t=l;
else merge(l,r->l,r->l), t=r;
upd(t);
}
void dfs(int x, int par) {
p[x]=par;
level[x]=level[par]+1;
for (auto s : adj[x]) {
if (s.first==par) continue;
w[s.first]=s.second;
merge(tr[x],new node(s.second),tr[x]);
dfs(s.first,x);
}
}
void cal(int x, int want) {
pnode A,B,C;
//find dp[x][0], don't cut the edge above it
split1(tr[x],A,B,adj[x].size()-want-de[x]);
if (A) dp[x][0]=A->sum+c[x];
else dp[x][0]=c[x];
merge(A,B,tr[x]);
if (x) {
//find dp[x][1], cut the edge above it
split1(tr[x],A,B,adj[x].size()-want-1-de[x]);
if (A) dp[x][1]=A->sum+w[x]+c[x];
else dp[x][1]=w[x]+c[x];
merge(A,B,tr[x]);
//replace the value of the parent by dp[x][1]-dp[x][0]
int par=p[x];
split2(tr[par],A,B,w[x]);
split1(B,C,B,1);
merge(A,B,tr[par]);
ll nw=dp[x][1]-dp[x][0];
if (nw<=0) {
c[par]+=dp[x][1];
++de[par];
} else {
split2(tr[par],A,B,nw+1);
merge(A,new node(nw),A);
merge(A,B,tr[par]);
c[par]+=dp[x][0];
}
}
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n=N;
for (int i=0; i<n-1; ++i) {
adj[U[i]].push_back(pii(V[i],W[i]));
adj[V[i]].push_back(pii(U[i],W[i]));
++d[U[i]]; ++d[V[i]];
}
for (int i=0; i<n; ++i) deg.push_back(i), sort(adj[i].begin(),adj[i].end(),comp);
sort(deg.begin(),deg.end(),comp3);
dfs(0,0);
p[0]=-1;
for (int i=1; i<n; ++i) dp[i][1]=w[i], sum+=w[i];
ans.push_back(sum);
for (int i=1; i<n; ++i) {
sum=0;
while (!deg.empty()) {
if (d[deg.back()]<i+1) deg.pop_back();
else break;
}
vector<int> v;
for (auto s : deg) v.push_back(s);
sort(v.begin(),v.end(),comp2);
for (auto s : v) {
cal(s,i);
if (s==0) sum+=dp[s][0];
else if (d[p[s]]<=i) sum+=min(dp[s][0],dp[s][1]);
}
ans.push_back(sum);
//reset
for (auto s : v) {
c[s]=de[s]=0;
if (s==0) continue;
int par=p[s];
pnode A,B,C;
if (dp[s][1]>dp[s][0]) {
split2(tr[par],A,B,dp[s][1]-dp[s][0]);
split1(B,C,B,1);
merge(A,B,tr[par]);
}
split2(tr[par],A,B,w[s]+1);
merge(A,new node(w[s]),A);
merge(A,B,tr[par]);
}
}
return ans;
}
Compilation message
roads.cpp: In constructor 'node::node(ll)':
roads.cpp:19:12: warning: 'node::sum' will be initialized after [-Wreorder]
19 | ll val,sum;
| ^~~
roads.cpp:18:13: warning: 'int node::prior' [-Wreorder]
18 | int cnt,prior;
| ^~~~~
roads.cpp:22:5: warning: when initialized here [-Wreorder]
22 | node(ll v) : cnt(1), val(v), sum(v), prior(rand()), l(NULL), r(NULL) {}
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2664 KB |
Output is correct |
2 |
Correct |
6 ms |
3028 KB |
Output is correct |
3 |
Correct |
4 ms |
3060 KB |
Output is correct |
4 |
Correct |
5 ms |
3028 KB |
Output is correct |
5 |
Correct |
3 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
6 ms |
2928 KB |
Output is correct |
9 |
Correct |
5 ms |
3028 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
95 ms |
13272 KB |
Output is correct |
13 |
Correct |
148 ms |
20172 KB |
Output is correct |
14 |
Correct |
137 ms |
19236 KB |
Output is correct |
15 |
Correct |
138 ms |
20920 KB |
Output is correct |
16 |
Correct |
162 ms |
21216 KB |
Output is correct |
17 |
Correct |
143 ms |
21404 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
115 ms |
18540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
91 ms |
34332 KB |
Output is correct |
3 |
Correct |
96 ms |
37528 KB |
Output is correct |
4 |
Correct |
103 ms |
40292 KB |
Output is correct |
5 |
Correct |
90 ms |
39064 KB |
Output is correct |
6 |
Correct |
5 ms |
3284 KB |
Output is correct |
7 |
Correct |
5 ms |
3444 KB |
Output is correct |
8 |
Correct |
5 ms |
3284 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
3 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2660 KB |
Output is correct |
12 |
Correct |
52 ms |
24772 KB |
Output is correct |
13 |
Correct |
88 ms |
39020 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
78 ms |
34656 KB |
Output is correct |
16 |
Correct |
87 ms |
38124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2664 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2752 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
2 ms |
2664 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2672 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2664 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2752 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
2 ms |
2664 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2772 KB |
Output is correct |
12 |
Correct |
2 ms |
2772 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2672 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2664 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
4 ms |
3028 KB |
Output is correct |
24 |
Correct |
5 ms |
3284 KB |
Output is correct |
25 |
Correct |
3 ms |
3184 KB |
Output is correct |
26 |
Correct |
5 ms |
3284 KB |
Output is correct |
27 |
Correct |
5 ms |
3156 KB |
Output is correct |
28 |
Correct |
6 ms |
3284 KB |
Output is correct |
29 |
Correct |
4 ms |
3156 KB |
Output is correct |
30 |
Correct |
5 ms |
3156 KB |
Output is correct |
31 |
Correct |
5 ms |
3156 KB |
Output is correct |
32 |
Correct |
5 ms |
3156 KB |
Output is correct |
33 |
Correct |
4 ms |
3312 KB |
Output is correct |
34 |
Correct |
5 ms |
3412 KB |
Output is correct |
35 |
Correct |
4 ms |
3284 KB |
Output is correct |
36 |
Correct |
4 ms |
3028 KB |
Output is correct |
37 |
Correct |
4 ms |
3028 KB |
Output is correct |
38 |
Correct |
4 ms |
3028 KB |
Output is correct |
39 |
Correct |
2 ms |
2772 KB |
Output is correct |
40 |
Correct |
2 ms |
2644 KB |
Output is correct |
41 |
Correct |
3 ms |
2644 KB |
Output is correct |
42 |
Correct |
3 ms |
2664 KB |
Output is correct |
43 |
Correct |
2 ms |
2772 KB |
Output is correct |
44 |
Correct |
2 ms |
2644 KB |
Output is correct |
45 |
Correct |
2 ms |
2644 KB |
Output is correct |
46 |
Correct |
2 ms |
2644 KB |
Output is correct |
47 |
Correct |
2 ms |
2644 KB |
Output is correct |
48 |
Correct |
2 ms |
2772 KB |
Output is correct |
49 |
Correct |
2 ms |
2772 KB |
Output is correct |
50 |
Correct |
2 ms |
2644 KB |
Output is correct |
51 |
Correct |
3 ms |
2644 KB |
Output is correct |
52 |
Correct |
2 ms |
2664 KB |
Output is correct |
53 |
Correct |
3 ms |
3060 KB |
Output is correct |
54 |
Correct |
4 ms |
3156 KB |
Output is correct |
55 |
Correct |
5 ms |
3156 KB |
Output is correct |
56 |
Correct |
3 ms |
2900 KB |
Output is correct |
57 |
Correct |
4 ms |
3072 KB |
Output is correct |
58 |
Correct |
2 ms |
2644 KB |
Output is correct |
59 |
Correct |
2 ms |
2644 KB |
Output is correct |
60 |
Correct |
2 ms |
2644 KB |
Output is correct |
61 |
Correct |
3 ms |
2664 KB |
Output is correct |
62 |
Correct |
2 ms |
2732 KB |
Output is correct |
63 |
Correct |
2 ms |
2644 KB |
Output is correct |
64 |
Correct |
4 ms |
3156 KB |
Output is correct |
65 |
Correct |
4 ms |
3156 KB |
Output is correct |
66 |
Correct |
5 ms |
3156 KB |
Output is correct |
67 |
Correct |
5 ms |
3184 KB |
Output is correct |
68 |
Correct |
4 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
27464 KB |
Output is correct |
2 |
Correct |
146 ms |
27064 KB |
Output is correct |
3 |
Correct |
209 ms |
27308 KB |
Output is correct |
4 |
Correct |
150 ms |
28356 KB |
Output is correct |
5 |
Correct |
181 ms |
27468 KB |
Output is correct |
6 |
Correct |
178 ms |
25832 KB |
Output is correct |
7 |
Correct |
181 ms |
27560 KB |
Output is correct |
8 |
Correct |
156 ms |
23372 KB |
Output is correct |
9 |
Correct |
135 ms |
30460 KB |
Output is correct |
10 |
Correct |
150 ms |
27284 KB |
Output is correct |
11 |
Correct |
194 ms |
27328 KB |
Output is correct |
12 |
Correct |
169 ms |
25412 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
75 ms |
34644 KB |
Output is correct |
15 |
Correct |
83 ms |
38084 KB |
Output is correct |
16 |
Correct |
4 ms |
3188 KB |
Output is correct |
17 |
Correct |
4 ms |
3284 KB |
Output is correct |
18 |
Correct |
5 ms |
3188 KB |
Output is correct |
19 |
Correct |
5 ms |
3156 KB |
Output is correct |
20 |
Correct |
5 ms |
3188 KB |
Output is correct |
21 |
Correct |
108 ms |
18520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
27464 KB |
Output is correct |
2 |
Correct |
146 ms |
27064 KB |
Output is correct |
3 |
Correct |
209 ms |
27308 KB |
Output is correct |
4 |
Correct |
150 ms |
28356 KB |
Output is correct |
5 |
Correct |
181 ms |
27468 KB |
Output is correct |
6 |
Correct |
178 ms |
25832 KB |
Output is correct |
7 |
Correct |
181 ms |
27560 KB |
Output is correct |
8 |
Correct |
156 ms |
23372 KB |
Output is correct |
9 |
Correct |
135 ms |
30460 KB |
Output is correct |
10 |
Correct |
150 ms |
27284 KB |
Output is correct |
11 |
Correct |
194 ms |
27328 KB |
Output is correct |
12 |
Correct |
169 ms |
25412 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
75 ms |
34644 KB |
Output is correct |
15 |
Correct |
83 ms |
38084 KB |
Output is correct |
16 |
Correct |
4 ms |
3188 KB |
Output is correct |
17 |
Correct |
4 ms |
3284 KB |
Output is correct |
18 |
Correct |
5 ms |
3188 KB |
Output is correct |
19 |
Correct |
5 ms |
3156 KB |
Output is correct |
20 |
Correct |
5 ms |
3188 KB |
Output is correct |
21 |
Correct |
108 ms |
18520 KB |
Output is correct |
22 |
Correct |
3 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
2 ms |
2644 KB |
Output is correct |
25 |
Correct |
142 ms |
26052 KB |
Output is correct |
26 |
Correct |
118 ms |
23688 KB |
Output is correct |
27 |
Correct |
170 ms |
29808 KB |
Output is correct |
28 |
Correct |
285 ms |
29492 KB |
Output is correct |
29 |
Correct |
215 ms |
27392 KB |
Output is correct |
30 |
Correct |
250 ms |
27232 KB |
Output is correct |
31 |
Correct |
285 ms |
28384 KB |
Output is correct |
32 |
Correct |
160 ms |
27016 KB |
Output is correct |
33 |
Correct |
162 ms |
27932 KB |
Output is correct |
34 |
Correct |
262 ms |
29612 KB |
Output is correct |
35 |
Correct |
166 ms |
34092 KB |
Output is correct |
36 |
Correct |
262 ms |
29384 KB |
Output is correct |
37 |
Correct |
282 ms |
26824 KB |
Output is correct |
38 |
Correct |
53 ms |
24808 KB |
Output is correct |
39 |
Correct |
86 ms |
39024 KB |
Output is correct |
40 |
Correct |
4 ms |
3056 KB |
Output is correct |
41 |
Correct |
5 ms |
3192 KB |
Output is correct |
42 |
Correct |
6 ms |
3156 KB |
Output is correct |
43 |
Correct |
4 ms |
2928 KB |
Output is correct |
44 |
Correct |
4 ms |
3028 KB |
Output is correct |
45 |
Correct |
2 ms |
2644 KB |
Output is correct |
46 |
Correct |
2 ms |
2644 KB |
Output is correct |
47 |
Correct |
2 ms |
2660 KB |
Output is correct |
48 |
Correct |
2 ms |
2644 KB |
Output is correct |
49 |
Correct |
2 ms |
2772 KB |
Output is correct |
50 |
Correct |
68 ms |
13296 KB |
Output is correct |
51 |
Correct |
126 ms |
20176 KB |
Output is correct |
52 |
Correct |
169 ms |
27580 KB |
Output is correct |
53 |
Correct |
145 ms |
27048 KB |
Output is correct |
54 |
Correct |
193 ms |
27368 KB |
Output is correct |
55 |
Correct |
146 ms |
28356 KB |
Output is correct |
56 |
Correct |
184 ms |
27372 KB |
Output is correct |
57 |
Correct |
179 ms |
25832 KB |
Output is correct |
58 |
Correct |
170 ms |
27552 KB |
Output is correct |
59 |
Correct |
160 ms |
23476 KB |
Output is correct |
60 |
Correct |
138 ms |
30408 KB |
Output is correct |
61 |
Correct |
163 ms |
27264 KB |
Output is correct |
62 |
Correct |
201 ms |
27416 KB |
Output is correct |
63 |
Correct |
167 ms |
25416 KB |
Output is correct |
64 |
Correct |
2 ms |
2644 KB |
Output is correct |
65 |
Correct |
75 ms |
34576 KB |
Output is correct |
66 |
Correct |
81 ms |
38088 KB |
Output is correct |
67 |
Correct |
4 ms |
3184 KB |
Output is correct |
68 |
Correct |
5 ms |
3220 KB |
Output is correct |
69 |
Correct |
5 ms |
3156 KB |
Output is correct |
70 |
Correct |
5 ms |
3156 KB |
Output is correct |
71 |
Correct |
4 ms |
3088 KB |
Output is correct |
72 |
Correct |
103 ms |
18580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2664 KB |
Output is correct |
2 |
Correct |
6 ms |
3028 KB |
Output is correct |
3 |
Correct |
4 ms |
3060 KB |
Output is correct |
4 |
Correct |
5 ms |
3028 KB |
Output is correct |
5 |
Correct |
3 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
6 ms |
2928 KB |
Output is correct |
9 |
Correct |
5 ms |
3028 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
95 ms |
13272 KB |
Output is correct |
13 |
Correct |
148 ms |
20172 KB |
Output is correct |
14 |
Correct |
137 ms |
19236 KB |
Output is correct |
15 |
Correct |
138 ms |
20920 KB |
Output is correct |
16 |
Correct |
162 ms |
21216 KB |
Output is correct |
17 |
Correct |
143 ms |
21404 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
115 ms |
18540 KB |
Output is correct |
20 |
Correct |
3 ms |
2644 KB |
Output is correct |
21 |
Correct |
91 ms |
34332 KB |
Output is correct |
22 |
Correct |
96 ms |
37528 KB |
Output is correct |
23 |
Correct |
103 ms |
40292 KB |
Output is correct |
24 |
Correct |
90 ms |
39064 KB |
Output is correct |
25 |
Correct |
5 ms |
3284 KB |
Output is correct |
26 |
Correct |
5 ms |
3444 KB |
Output is correct |
27 |
Correct |
5 ms |
3284 KB |
Output is correct |
28 |
Correct |
2 ms |
2772 KB |
Output is correct |
29 |
Correct |
3 ms |
2772 KB |
Output is correct |
30 |
Correct |
2 ms |
2660 KB |
Output is correct |
31 |
Correct |
52 ms |
24772 KB |
Output is correct |
32 |
Correct |
88 ms |
39020 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
78 ms |
34656 KB |
Output is correct |
35 |
Correct |
87 ms |
38124 KB |
Output is correct |
36 |
Correct |
2 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
2 ms |
2664 KB |
Output is correct |
39 |
Correct |
2 ms |
2644 KB |
Output is correct |
40 |
Correct |
2 ms |
2752 KB |
Output is correct |
41 |
Correct |
2 ms |
2772 KB |
Output is correct |
42 |
Correct |
2 ms |
2664 KB |
Output is correct |
43 |
Correct |
2 ms |
2644 KB |
Output is correct |
44 |
Correct |
2 ms |
2644 KB |
Output is correct |
45 |
Correct |
2 ms |
2644 KB |
Output is correct |
46 |
Correct |
2 ms |
2772 KB |
Output is correct |
47 |
Correct |
2 ms |
2772 KB |
Output is correct |
48 |
Correct |
2 ms |
2644 KB |
Output is correct |
49 |
Correct |
2 ms |
2672 KB |
Output is correct |
50 |
Correct |
2 ms |
2644 KB |
Output is correct |
51 |
Correct |
2 ms |
2644 KB |
Output is correct |
52 |
Correct |
2 ms |
2644 KB |
Output is correct |
53 |
Correct |
2 ms |
2644 KB |
Output is correct |
54 |
Correct |
2 ms |
2644 KB |
Output is correct |
55 |
Correct |
2 ms |
2644 KB |
Output is correct |
56 |
Correct |
2 ms |
2664 KB |
Output is correct |
57 |
Correct |
2 ms |
2644 KB |
Output is correct |
58 |
Correct |
4 ms |
3028 KB |
Output is correct |
59 |
Correct |
5 ms |
3284 KB |
Output is correct |
60 |
Correct |
3 ms |
3184 KB |
Output is correct |
61 |
Correct |
5 ms |
3284 KB |
Output is correct |
62 |
Correct |
5 ms |
3156 KB |
Output is correct |
63 |
Correct |
6 ms |
3284 KB |
Output is correct |
64 |
Correct |
4 ms |
3156 KB |
Output is correct |
65 |
Correct |
5 ms |
3156 KB |
Output is correct |
66 |
Correct |
5 ms |
3156 KB |
Output is correct |
67 |
Correct |
5 ms |
3156 KB |
Output is correct |
68 |
Correct |
4 ms |
3312 KB |
Output is correct |
69 |
Correct |
5 ms |
3412 KB |
Output is correct |
70 |
Correct |
4 ms |
3284 KB |
Output is correct |
71 |
Correct |
4 ms |
3028 KB |
Output is correct |
72 |
Correct |
4 ms |
3028 KB |
Output is correct |
73 |
Correct |
4 ms |
3028 KB |
Output is correct |
74 |
Correct |
2 ms |
2772 KB |
Output is correct |
75 |
Correct |
2 ms |
2644 KB |
Output is correct |
76 |
Correct |
3 ms |
2644 KB |
Output is correct |
77 |
Correct |
3 ms |
2664 KB |
Output is correct |
78 |
Correct |
2 ms |
2772 KB |
Output is correct |
79 |
Correct |
2 ms |
2644 KB |
Output is correct |
80 |
Correct |
2 ms |
2644 KB |
Output is correct |
81 |
Correct |
2 ms |
2644 KB |
Output is correct |
82 |
Correct |
2 ms |
2644 KB |
Output is correct |
83 |
Correct |
2 ms |
2772 KB |
Output is correct |
84 |
Correct |
2 ms |
2772 KB |
Output is correct |
85 |
Correct |
2 ms |
2644 KB |
Output is correct |
86 |
Correct |
3 ms |
2644 KB |
Output is correct |
87 |
Correct |
2 ms |
2664 KB |
Output is correct |
88 |
Correct |
3 ms |
3060 KB |
Output is correct |
89 |
Correct |
4 ms |
3156 KB |
Output is correct |
90 |
Correct |
5 ms |
3156 KB |
Output is correct |
91 |
Correct |
3 ms |
2900 KB |
Output is correct |
92 |
Correct |
4 ms |
3072 KB |
Output is correct |
93 |
Correct |
2 ms |
2644 KB |
Output is correct |
94 |
Correct |
2 ms |
2644 KB |
Output is correct |
95 |
Correct |
2 ms |
2644 KB |
Output is correct |
96 |
Correct |
3 ms |
2664 KB |
Output is correct |
97 |
Correct |
2 ms |
2732 KB |
Output is correct |
98 |
Correct |
2 ms |
2644 KB |
Output is correct |
99 |
Correct |
4 ms |
3156 KB |
Output is correct |
100 |
Correct |
4 ms |
3156 KB |
Output is correct |
101 |
Correct |
5 ms |
3156 KB |
Output is correct |
102 |
Correct |
5 ms |
3184 KB |
Output is correct |
103 |
Correct |
4 ms |
3156 KB |
Output is correct |
104 |
Correct |
145 ms |
27464 KB |
Output is correct |
105 |
Correct |
146 ms |
27064 KB |
Output is correct |
106 |
Correct |
209 ms |
27308 KB |
Output is correct |
107 |
Correct |
150 ms |
28356 KB |
Output is correct |
108 |
Correct |
181 ms |
27468 KB |
Output is correct |
109 |
Correct |
178 ms |
25832 KB |
Output is correct |
110 |
Correct |
181 ms |
27560 KB |
Output is correct |
111 |
Correct |
156 ms |
23372 KB |
Output is correct |
112 |
Correct |
135 ms |
30460 KB |
Output is correct |
113 |
Correct |
150 ms |
27284 KB |
Output is correct |
114 |
Correct |
194 ms |
27328 KB |
Output is correct |
115 |
Correct |
169 ms |
25412 KB |
Output is correct |
116 |
Correct |
2 ms |
2644 KB |
Output is correct |
117 |
Correct |
75 ms |
34644 KB |
Output is correct |
118 |
Correct |
83 ms |
38084 KB |
Output is correct |
119 |
Correct |
4 ms |
3188 KB |
Output is correct |
120 |
Correct |
4 ms |
3284 KB |
Output is correct |
121 |
Correct |
5 ms |
3188 KB |
Output is correct |
122 |
Correct |
5 ms |
3156 KB |
Output is correct |
123 |
Correct |
5 ms |
3188 KB |
Output is correct |
124 |
Correct |
108 ms |
18520 KB |
Output is correct |
125 |
Correct |
3 ms |
2644 KB |
Output is correct |
126 |
Correct |
2 ms |
2644 KB |
Output is correct |
127 |
Correct |
2 ms |
2644 KB |
Output is correct |
128 |
Correct |
142 ms |
26052 KB |
Output is correct |
129 |
Correct |
118 ms |
23688 KB |
Output is correct |
130 |
Correct |
170 ms |
29808 KB |
Output is correct |
131 |
Correct |
285 ms |
29492 KB |
Output is correct |
132 |
Correct |
215 ms |
27392 KB |
Output is correct |
133 |
Correct |
250 ms |
27232 KB |
Output is correct |
134 |
Correct |
285 ms |
28384 KB |
Output is correct |
135 |
Correct |
160 ms |
27016 KB |
Output is correct |
136 |
Correct |
162 ms |
27932 KB |
Output is correct |
137 |
Correct |
262 ms |
29612 KB |
Output is correct |
138 |
Correct |
166 ms |
34092 KB |
Output is correct |
139 |
Correct |
262 ms |
29384 KB |
Output is correct |
140 |
Correct |
282 ms |
26824 KB |
Output is correct |
141 |
Correct |
53 ms |
24808 KB |
Output is correct |
142 |
Correct |
86 ms |
39024 KB |
Output is correct |
143 |
Correct |
4 ms |
3056 KB |
Output is correct |
144 |
Correct |
5 ms |
3192 KB |
Output is correct |
145 |
Correct |
6 ms |
3156 KB |
Output is correct |
146 |
Correct |
4 ms |
2928 KB |
Output is correct |
147 |
Correct |
4 ms |
3028 KB |
Output is correct |
148 |
Correct |
2 ms |
2644 KB |
Output is correct |
149 |
Correct |
2 ms |
2644 KB |
Output is correct |
150 |
Correct |
2 ms |
2660 KB |
Output is correct |
151 |
Correct |
2 ms |
2644 KB |
Output is correct |
152 |
Correct |
2 ms |
2772 KB |
Output is correct |
153 |
Correct |
68 ms |
13296 KB |
Output is correct |
154 |
Correct |
126 ms |
20176 KB |
Output is correct |
155 |
Correct |
169 ms |
27580 KB |
Output is correct |
156 |
Correct |
145 ms |
27048 KB |
Output is correct |
157 |
Correct |
193 ms |
27368 KB |
Output is correct |
158 |
Correct |
146 ms |
28356 KB |
Output is correct |
159 |
Correct |
184 ms |
27372 KB |
Output is correct |
160 |
Correct |
179 ms |
25832 KB |
Output is correct |
161 |
Correct |
170 ms |
27552 KB |
Output is correct |
162 |
Correct |
160 ms |
23476 KB |
Output is correct |
163 |
Correct |
138 ms |
30408 KB |
Output is correct |
164 |
Correct |
163 ms |
27264 KB |
Output is correct |
165 |
Correct |
201 ms |
27416 KB |
Output is correct |
166 |
Correct |
167 ms |
25416 KB |
Output is correct |
167 |
Correct |
2 ms |
2644 KB |
Output is correct |
168 |
Correct |
75 ms |
34576 KB |
Output is correct |
169 |
Correct |
81 ms |
38088 KB |
Output is correct |
170 |
Correct |
4 ms |
3184 KB |
Output is correct |
171 |
Correct |
5 ms |
3220 KB |
Output is correct |
172 |
Correct |
5 ms |
3156 KB |
Output is correct |
173 |
Correct |
5 ms |
3156 KB |
Output is correct |
174 |
Correct |
4 ms |
3088 KB |
Output is correct |
175 |
Correct |
103 ms |
18580 KB |
Output is correct |
176 |
Correct |
2 ms |
2644 KB |
Output is correct |
177 |
Correct |
169 ms |
30652 KB |
Output is correct |
178 |
Correct |
125 ms |
24280 KB |
Output is correct |
179 |
Correct |
231 ms |
31992 KB |
Output is correct |
180 |
Correct |
234 ms |
28888 KB |
Output is correct |
181 |
Correct |
183 ms |
28264 KB |
Output is correct |
182 |
Correct |
229 ms |
32120 KB |
Output is correct |
183 |
Correct |
233 ms |
31852 KB |
Output is correct |
184 |
Correct |
242 ms |
27564 KB |
Output is correct |
185 |
Correct |
232 ms |
27960 KB |
Output is correct |
186 |
Correct |
227 ms |
26844 KB |
Output is correct |
187 |
Correct |
182 ms |
26696 KB |
Output is correct |
188 |
Correct |
155 ms |
29636 KB |
Output is correct |
189 |
Correct |
165 ms |
28304 KB |
Output is correct |
190 |
Correct |
248 ms |
30500 KB |
Output is correct |
191 |
Correct |
218 ms |
32004 KB |
Output is correct |
192 |
Correct |
232 ms |
27848 KB |
Output is correct |
193 |
Correct |
270 ms |
28332 KB |
Output is correct |
194 |
Correct |
205 ms |
28276 KB |
Output is correct |
195 |
Correct |
76 ms |
34288 KB |
Output is correct |
196 |
Correct |
84 ms |
37496 KB |
Output is correct |
197 |
Correct |
92 ms |
40268 KB |
Output is correct |
198 |
Correct |
89 ms |
38984 KB |
Output is correct |
199 |
Correct |
3 ms |
3028 KB |
Output is correct |
200 |
Correct |
4 ms |
3192 KB |
Output is correct |
201 |
Correct |
4 ms |
3184 KB |
Output is correct |
202 |
Correct |
5 ms |
3284 KB |
Output is correct |
203 |
Correct |
5 ms |
3240 KB |
Output is correct |
204 |
Correct |
6 ms |
3284 KB |
Output is correct |
205 |
Correct |
4 ms |
3156 KB |
Output is correct |
206 |
Correct |
5 ms |
3180 KB |
Output is correct |
207 |
Correct |
5 ms |
3156 KB |
Output is correct |
208 |
Correct |
4 ms |
3156 KB |
Output is correct |
209 |
Correct |
3 ms |
3284 KB |
Output is correct |
210 |
Correct |
3 ms |
3412 KB |
Output is correct |
211 |
Correct |
3 ms |
3284 KB |
Output is correct |
212 |
Correct |
4 ms |
3028 KB |
Output is correct |
213 |
Correct |
4 ms |
3028 KB |
Output is correct |
214 |
Correct |
4 ms |
3028 KB |
Output is correct |
215 |
Correct |
2 ms |
2644 KB |
Output is correct |
216 |
Correct |
2 ms |
2644 KB |
Output is correct |
217 |
Correct |
2 ms |
2644 KB |
Output is correct |
218 |
Correct |
2 ms |
2644 KB |
Output is correct |
219 |
Correct |
3 ms |
2644 KB |
Output is correct |
220 |
Correct |
2 ms |
2644 KB |
Output is correct |
221 |
Correct |
2 ms |
2644 KB |
Output is correct |
222 |
Correct |
2 ms |
2644 KB |
Output is correct |
223 |
Correct |
2 ms |
2644 KB |
Output is correct |
224 |
Correct |
2 ms |
2772 KB |
Output is correct |
225 |
Correct |
2 ms |
2772 KB |
Output is correct |
226 |
Correct |
2 ms |
2644 KB |
Output is correct |
227 |
Correct |
2 ms |
2656 KB |
Output is correct |
228 |
Correct |
2 ms |
2644 KB |
Output is correct |
229 |
Correct |
151 ms |
26124 KB |
Output is correct |
230 |
Correct |
114 ms |
23728 KB |
Output is correct |
231 |
Correct |
163 ms |
29768 KB |
Output is correct |
232 |
Correct |
278 ms |
29524 KB |
Output is correct |
233 |
Correct |
207 ms |
27308 KB |
Output is correct |
234 |
Correct |
245 ms |
27232 KB |
Output is correct |
235 |
Correct |
294 ms |
28492 KB |
Output is correct |
236 |
Correct |
165 ms |
27036 KB |
Output is correct |
237 |
Correct |
162 ms |
27964 KB |
Output is correct |
238 |
Correct |
240 ms |
29612 KB |
Output is correct |
239 |
Correct |
165 ms |
34116 KB |
Output is correct |
240 |
Correct |
256 ms |
29424 KB |
Output is correct |
241 |
Correct |
252 ms |
26912 KB |
Output is correct |
242 |
Correct |
49 ms |
24748 KB |
Output is correct |
243 |
Correct |
85 ms |
39020 KB |
Output is correct |
244 |
Correct |
4 ms |
3060 KB |
Output is correct |
245 |
Correct |
5 ms |
3156 KB |
Output is correct |
246 |
Correct |
5 ms |
3156 KB |
Output is correct |
247 |
Correct |
4 ms |
2956 KB |
Output is correct |
248 |
Correct |
5 ms |
3028 KB |
Output is correct |
249 |
Correct |
2 ms |
2644 KB |
Output is correct |
250 |
Correct |
2 ms |
2644 KB |
Output is correct |
251 |
Correct |
2 ms |
2664 KB |
Output is correct |
252 |
Correct |
2 ms |
2644 KB |
Output is correct |
253 |
Correct |
3 ms |
2644 KB |
Output is correct |
254 |
Correct |
78 ms |
13224 KB |
Output is correct |
255 |
Correct |
129 ms |
20196 KB |
Output is correct |
256 |
Correct |
133 ms |
19248 KB |
Output is correct |
257 |
Correct |
141 ms |
20916 KB |
Output is correct |
258 |
Correct |
141 ms |
21304 KB |
Output is correct |
259 |
Correct |
122 ms |
21416 KB |
Output is correct |
260 |
Correct |
142 ms |
27484 KB |
Output is correct |
261 |
Correct |
166 ms |
27044 KB |
Output is correct |
262 |
Correct |
199 ms |
27376 KB |
Output is correct |
263 |
Correct |
162 ms |
28348 KB |
Output is correct |
264 |
Correct |
179 ms |
27356 KB |
Output is correct |
265 |
Correct |
180 ms |
25832 KB |
Output is correct |
266 |
Correct |
182 ms |
27536 KB |
Output is correct |
267 |
Correct |
150 ms |
23456 KB |
Output is correct |
268 |
Correct |
154 ms |
30476 KB |
Output is correct |
269 |
Correct |
182 ms |
27344 KB |
Output is correct |
270 |
Correct |
200 ms |
27368 KB |
Output is correct |
271 |
Correct |
185 ms |
25424 KB |
Output is correct |
272 |
Correct |
2 ms |
2644 KB |
Output is correct |
273 |
Correct |
81 ms |
34636 KB |
Output is correct |
274 |
Correct |
85 ms |
38088 KB |
Output is correct |
275 |
Correct |
4 ms |
3188 KB |
Output is correct |
276 |
Correct |
4 ms |
3184 KB |
Output is correct |
277 |
Correct |
5 ms |
3156 KB |
Output is correct |
278 |
Correct |
5 ms |
3156 KB |
Output is correct |
279 |
Correct |
4 ms |
3156 KB |
Output is correct |
280 |
Correct |
103 ms |
18496 KB |
Output is correct |