#include "roads.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=100010;
int N;
vector <pll> v[mxN], ch[mxN];
vector <ll> seg[mxN], d[mxN];
int sub[mxN];
int u[mxN], dd[mxN];
void dfs0(int now, int pre)
{
sub[now]=1;
for(auto [nxt, x] : v[now]) if(nxt!=pre)
{
dfs0(nxt, now);
ch[now].emplace_back(nxt, x);
sub[now]+=sub[nxt];
}
if(ch[now].empty())
{
u[now]=dd[now]=now;
return;
}
sort(ch[now].begin(), ch[now].end(), [](pll a, pll b){return sub[a.fi]>sub[b.fi];});
dd[now]=dd[ch[now][0].fi];
u[dd[now]]=now;
}
void upd(int typ, int idx, int s1, int e1, int s2, int e2, ll val)
{
if(s1>e2 || s2>e1) return;
if(s2<=s1 && e1<=e2)
{
seg[typ][idx]+=val;
return;
}
int mid=(s1+e1)/2;
upd(typ, 2*idx, s1, mid, s2, e2, val);
upd(typ, 2*idx+1, mid+1, e1, s2, e2, val);
}
ll solv(int typ, int idx, int s, int e, int pos)
{
if(s==e) return seg[typ][idx];
int mid=(s+e)/2;
if(pos<=mid) return seg[typ][idx]+solv(typ, 2*idx, s, mid, pos);
else return seg[typ][idx]+solv(typ, 2*idx+1, mid+1, e, pos);
}
void dfs1(int now)
{
d[now].resize(ch[now].size()+1);
if(ch[now].empty())
{
seg[now].resize(4*sub[u[now]]);
return;
}
for(auto [nxt, x] : ch[now]) dfs1(nxt);
int fc=ch[now][0].fi;
u[now]=u[fc];
upd(fc, 1, 1, sub[u[fc]], sub[fc]+1, sub[now], solv(fc, 1, 1, sub[u[fc]], sub[fc]));
swap(seg[now], seg[fc]);
for(auto [nxt, x] : ch[now]) if(nxt!=fc)
{
for(int i=1;i<=sub[nxt];i++)
{
upd(now, 1, 1, sub[u[now]], i, i, solv(nxt, 1, 1, sub[nxt], i));
}
upd(now, 1, 1, sub[u[now]], sub[nxt]+1, sub[now], solv(nxt, 1, 1, sub[nxt], sub[nxt]));
}
multiset <ll> lo, hi;
vector <pll> ct;
ct=ch[now];
sort(ct.begin(), ct.end(), [](pll a, pll b){return ch[a.fi].size()>ch[b.fi].size();});
ll tsum=0;
for(auto [nxt, x] : ct) tsum+=x;
fc=ct[0].fi;
int lim=max(ch[fc].size(), ch[now].size());
upd(now, 1, 1, sub[u[now]], lim+1, sub[now], tsum);
/*for(int i=1;i<=sub[u[now]];i++)
{
printf("dp[%d][%d]=%lld\n", now, i, solv(now, 1, 1, N, i));
}*/
ll del=0;
while(ct.size() && ch[ct.back().fi].empty())
{
hi.insert(ct.back().se);
del+=ct.back().se;
ct.pop_back();
}
for(int i=1;i<=lim;i++)
{
while(hi.size()<i && lo.size())
{
hi.insert(*lo.rbegin());
del+=*lo.rbegin();
auto it=lo.end(); it--;
lo.erase(it);
}
while(hi.size()>i)
{
lo.insert(*hi.begin());
del-=*hi.begin();
hi.erase(hi.begin());
}
for(auto [nxt, x] : ct)
{
if(-d[nxt][i]+x>0)
{
hi.insert(-d[nxt][i]+x);
del+=(-d[nxt][i]+x);
}
}
vector <ll> tsh;
while(hi.size()>i)
{
tsh.push_back(*hi.begin());
del-=*hi.begin();
hi.erase(hi.begin());
}
/*printf("hi: ");
for(auto ele : hi) printf("%lld ", ele);
printf("\nlo: ");
for(auto ele : lo) printf("%lld ", ele);
printf("\n");*/
if(hi.size()==i && i<=ch[now].size()) d[now][i]=*hi.begin();
upd(now, 1, 1, sub[u[now]], i, i, del);
for(ll ele : tsh)
{
hi.insert(ele);
del+=ele;
}
for(auto [nxt, x] : ct)
{
if(-d[nxt][i]+x>0)
{
hi.erase(hi.find(-d[nxt][i]+x));
del-=(-d[nxt][i]+x);
}
}
while(ct.size() && ch[ct.back().fi].size()==i)
{
lo.insert(ct.back().se);
ct.pop_back();
}
while(lo.size() && hi.size() && *lo.rbegin()>*hi.begin())
{
hi.insert(*lo.rbegin());
del+=*lo.rbegin();
auto it=lo.end(); it--;
lo.erase(it);
}
}
/*for(int i=1;i<=sub[u[now]];i++)
{
printf("dp[%d][%d]=%lld\n", now, i, solv(now, 1, 1, N, i));
}*/
//printf("end %d\n", now);
}
vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
N=n;
for(int i=0;i<N-1;i++)
{
U[i]++;
V[i]++;
v[U[i]].emplace_back(V[i], W[i]);
v[V[i]].emplace_back(U[i], W[i]);
}
dfs0(1, -1);
//for(int i=1;i<=N;i++) printf("u[%d]=%d\n", i, u[i]);
dfs1(1);
//for(int i=1;i<=N;i++) for(int j=1;j<d[i].size();j++) printf("d[%d][%d]=%lld\n", i, j, d[i][j]);
vector <ll> ans;
ans.resize(N);
ll sum=0;
for(int ele : W) sum+=ele;
ans[0]=sum;
for(int i=1;i<N;i++) ans[i]=sum-solv(1, 1, 1, N, i);
return ans;
}
Compilation message
roads.cpp: In function 'void dfs1(int)':
roads.cpp:94:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | while(hi.size()<i && lo.size())
| ~~~~~~~~~^~
roads.cpp:101:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
101 | while(hi.size()>i)
| ~~~~~~~~~^~
roads.cpp:116:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
116 | while(hi.size()>i)
| ~~~~~~~~~^~
roads.cpp:127:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | if(hi.size()==i && i<=ch[now].size()) d[now][i]=*hi.begin();
| ~~~~~~~~~^~~
roads.cpp:127:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if(hi.size()==i && i<=ch[now].size()) d[now][i]=*hi.begin();
| ~^~~~~~~~~~~~~~~~
roads.cpp:142:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
142 | while(ct.size() && ch[ct.back().fi].size()==i)
| ~~~~~~~~~~~~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
8 ms |
10196 KB |
Output is correct |
3 |
Correct |
8 ms |
10196 KB |
Output is correct |
4 |
Correct |
8 ms |
10196 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9728 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
7 ms |
10164 KB |
Output is correct |
9 |
Correct |
8 ms |
10268 KB |
Output is correct |
10 |
Correct |
6 ms |
9684 KB |
Output is correct |
11 |
Correct |
6 ms |
9764 KB |
Output is correct |
12 |
Correct |
122 ms |
26420 KB |
Output is correct |
13 |
Correct |
189 ms |
37440 KB |
Output is correct |
14 |
Correct |
184 ms |
34364 KB |
Output is correct |
15 |
Correct |
197 ms |
37068 KB |
Output is correct |
16 |
Correct |
211 ms |
37592 KB |
Output is correct |
17 |
Correct |
210 ms |
37392 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
175 ms |
34748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
123 ms |
52212 KB |
Output is correct |
3 |
Correct |
144 ms |
57560 KB |
Output is correct |
4 |
Correct |
146 ms |
60928 KB |
Output is correct |
5 |
Correct |
154 ms |
60908 KB |
Output is correct |
6 |
Correct |
7 ms |
10580 KB |
Output is correct |
7 |
Correct |
8 ms |
10708 KB |
Output is correct |
8 |
Correct |
7 ms |
10628 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
95 ms |
40360 KB |
Output is correct |
13 |
Correct |
155 ms |
60892 KB |
Output is correct |
14 |
Correct |
6 ms |
9684 KB |
Output is correct |
15 |
Correct |
132 ms |
55808 KB |
Output is correct |
16 |
Correct |
145 ms |
61048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
7 ms |
9760 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9792 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9760 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9664 KB |
Output is correct |
17 |
Correct |
5 ms |
9720 KB |
Output is correct |
18 |
Correct |
7 ms |
9696 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
7 ms |
9760 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9792 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9760 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9664 KB |
Output is correct |
17 |
Correct |
5 ms |
9720 KB |
Output is correct |
18 |
Correct |
7 ms |
9696 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
5 ms |
9612 KB |
Output is correct |
23 |
Correct |
8 ms |
9940 KB |
Output is correct |
24 |
Correct |
10 ms |
10188 KB |
Output is correct |
25 |
Correct |
8 ms |
10156 KB |
Output is correct |
26 |
Correct |
8 ms |
10196 KB |
Output is correct |
27 |
Correct |
8 ms |
10196 KB |
Output is correct |
28 |
Correct |
8 ms |
10196 KB |
Output is correct |
29 |
Correct |
7 ms |
10196 KB |
Output is correct |
30 |
Correct |
8 ms |
10196 KB |
Output is correct |
31 |
Correct |
7 ms |
10268 KB |
Output is correct |
32 |
Correct |
8 ms |
10196 KB |
Output is correct |
33 |
Correct |
7 ms |
10580 KB |
Output is correct |
34 |
Correct |
8 ms |
10708 KB |
Output is correct |
35 |
Correct |
7 ms |
10580 KB |
Output is correct |
36 |
Correct |
8 ms |
10196 KB |
Output is correct |
37 |
Correct |
9 ms |
10196 KB |
Output is correct |
38 |
Correct |
8 ms |
10296 KB |
Output is correct |
39 |
Correct |
5 ms |
9684 KB |
Output is correct |
40 |
Correct |
5 ms |
9684 KB |
Output is correct |
41 |
Correct |
6 ms |
9684 KB |
Output is correct |
42 |
Correct |
5 ms |
9684 KB |
Output is correct |
43 |
Correct |
5 ms |
9684 KB |
Output is correct |
44 |
Correct |
5 ms |
9684 KB |
Output is correct |
45 |
Correct |
5 ms |
9684 KB |
Output is correct |
46 |
Correct |
5 ms |
9684 KB |
Output is correct |
47 |
Correct |
5 ms |
9684 KB |
Output is correct |
48 |
Correct |
5 ms |
9684 KB |
Output is correct |
49 |
Correct |
5 ms |
9812 KB |
Output is correct |
50 |
Correct |
6 ms |
9684 KB |
Output is correct |
51 |
Correct |
7 ms |
9732 KB |
Output is correct |
52 |
Correct |
6 ms |
9684 KB |
Output is correct |
53 |
Correct |
7 ms |
9996 KB |
Output is correct |
54 |
Correct |
10 ms |
10128 KB |
Output is correct |
55 |
Correct |
10 ms |
10212 KB |
Output is correct |
56 |
Correct |
7 ms |
10068 KB |
Output is correct |
57 |
Correct |
7 ms |
10196 KB |
Output is correct |
58 |
Correct |
5 ms |
9684 KB |
Output is correct |
59 |
Correct |
5 ms |
9660 KB |
Output is correct |
60 |
Correct |
5 ms |
9684 KB |
Output is correct |
61 |
Correct |
5 ms |
9684 KB |
Output is correct |
62 |
Correct |
6 ms |
9684 KB |
Output is correct |
63 |
Correct |
5 ms |
9684 KB |
Output is correct |
64 |
Correct |
8 ms |
10196 KB |
Output is correct |
65 |
Correct |
8 ms |
10196 KB |
Output is correct |
66 |
Correct |
8 ms |
10196 KB |
Output is correct |
67 |
Correct |
8 ms |
10196 KB |
Output is correct |
68 |
Correct |
8 ms |
10196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
206 ms |
37848 KB |
Output is correct |
2 |
Correct |
199 ms |
37480 KB |
Output is correct |
3 |
Correct |
193 ms |
39800 KB |
Output is correct |
4 |
Correct |
219 ms |
39820 KB |
Output is correct |
5 |
Correct |
184 ms |
37036 KB |
Output is correct |
6 |
Correct |
199 ms |
35120 KB |
Output is correct |
7 |
Correct |
187 ms |
36216 KB |
Output is correct |
8 |
Correct |
208 ms |
35456 KB |
Output is correct |
9 |
Correct |
185 ms |
42060 KB |
Output is correct |
10 |
Correct |
194 ms |
40428 KB |
Output is correct |
11 |
Correct |
194 ms |
39428 KB |
Output is correct |
12 |
Correct |
220 ms |
35184 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
133 ms |
55844 KB |
Output is correct |
15 |
Correct |
142 ms |
60892 KB |
Output is correct |
16 |
Correct |
8 ms |
10140 KB |
Output is correct |
17 |
Correct |
7 ms |
10196 KB |
Output is correct |
18 |
Correct |
8 ms |
10196 KB |
Output is correct |
19 |
Correct |
8 ms |
10196 KB |
Output is correct |
20 |
Correct |
7 ms |
10196 KB |
Output is correct |
21 |
Correct |
175 ms |
34820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
206 ms |
37848 KB |
Output is correct |
2 |
Correct |
199 ms |
37480 KB |
Output is correct |
3 |
Correct |
193 ms |
39800 KB |
Output is correct |
4 |
Correct |
219 ms |
39820 KB |
Output is correct |
5 |
Correct |
184 ms |
37036 KB |
Output is correct |
6 |
Correct |
199 ms |
35120 KB |
Output is correct |
7 |
Correct |
187 ms |
36216 KB |
Output is correct |
8 |
Correct |
208 ms |
35456 KB |
Output is correct |
9 |
Correct |
185 ms |
42060 KB |
Output is correct |
10 |
Correct |
194 ms |
40428 KB |
Output is correct |
11 |
Correct |
194 ms |
39428 KB |
Output is correct |
12 |
Correct |
220 ms |
35184 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
133 ms |
55844 KB |
Output is correct |
15 |
Correct |
142 ms |
60892 KB |
Output is correct |
16 |
Correct |
8 ms |
10140 KB |
Output is correct |
17 |
Correct |
7 ms |
10196 KB |
Output is correct |
18 |
Correct |
8 ms |
10196 KB |
Output is correct |
19 |
Correct |
8 ms |
10196 KB |
Output is correct |
20 |
Correct |
7 ms |
10196 KB |
Output is correct |
21 |
Correct |
175 ms |
34820 KB |
Output is correct |
22 |
Correct |
5 ms |
9684 KB |
Output is correct |
23 |
Correct |
5 ms |
9684 KB |
Output is correct |
24 |
Correct |
5 ms |
9684 KB |
Output is correct |
25 |
Correct |
170 ms |
34892 KB |
Output is correct |
26 |
Correct |
154 ms |
33536 KB |
Output is correct |
27 |
Correct |
205 ms |
40200 KB |
Output is correct |
28 |
Correct |
204 ms |
41420 KB |
Output is correct |
29 |
Correct |
171 ms |
36164 KB |
Output is correct |
30 |
Correct |
187 ms |
35488 KB |
Output is correct |
31 |
Correct |
206 ms |
35952 KB |
Output is correct |
32 |
Correct |
190 ms |
39780 KB |
Output is correct |
33 |
Correct |
200 ms |
37236 KB |
Output is correct |
34 |
Correct |
189 ms |
37608 KB |
Output is correct |
35 |
Correct |
198 ms |
44548 KB |
Output is correct |
36 |
Correct |
208 ms |
41548 KB |
Output is correct |
37 |
Correct |
209 ms |
34328 KB |
Output is correct |
38 |
Correct |
89 ms |
41228 KB |
Output is correct |
39 |
Correct |
146 ms |
62276 KB |
Output is correct |
40 |
Correct |
9 ms |
10068 KB |
Output is correct |
41 |
Correct |
8 ms |
10196 KB |
Output is correct |
42 |
Correct |
8 ms |
10196 KB |
Output is correct |
43 |
Correct |
7 ms |
10100 KB |
Output is correct |
44 |
Correct |
7 ms |
10196 KB |
Output is correct |
45 |
Correct |
5 ms |
9716 KB |
Output is correct |
46 |
Correct |
5 ms |
9684 KB |
Output is correct |
47 |
Correct |
6 ms |
9684 KB |
Output is correct |
48 |
Correct |
7 ms |
9684 KB |
Output is correct |
49 |
Correct |
5 ms |
9708 KB |
Output is correct |
50 |
Correct |
106 ms |
27028 KB |
Output is correct |
51 |
Correct |
194 ms |
38420 KB |
Output is correct |
52 |
Correct |
205 ms |
39132 KB |
Output is correct |
53 |
Correct |
196 ms |
38732 KB |
Output is correct |
54 |
Correct |
191 ms |
41200 KB |
Output is correct |
55 |
Correct |
215 ms |
41196 KB |
Output is correct |
56 |
Correct |
181 ms |
38548 KB |
Output is correct |
57 |
Correct |
193 ms |
36428 KB |
Output is correct |
58 |
Correct |
177 ms |
37620 KB |
Output is correct |
59 |
Correct |
203 ms |
36672 KB |
Output is correct |
60 |
Correct |
173 ms |
43264 KB |
Output is correct |
61 |
Correct |
193 ms |
41800 KB |
Output is correct |
62 |
Correct |
196 ms |
40524 KB |
Output is correct |
63 |
Correct |
204 ms |
36568 KB |
Output is correct |
64 |
Correct |
6 ms |
9704 KB |
Output is correct |
65 |
Correct |
127 ms |
57056 KB |
Output is correct |
66 |
Correct |
150 ms |
62388 KB |
Output is correct |
67 |
Correct |
8 ms |
10132 KB |
Output is correct |
68 |
Correct |
8 ms |
10196 KB |
Output is correct |
69 |
Correct |
8 ms |
10196 KB |
Output is correct |
70 |
Correct |
8 ms |
10228 KB |
Output is correct |
71 |
Correct |
8 ms |
10196 KB |
Output is correct |
72 |
Correct |
170 ms |
35732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
8 ms |
10196 KB |
Output is correct |
3 |
Correct |
8 ms |
10196 KB |
Output is correct |
4 |
Correct |
8 ms |
10196 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9728 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
7 ms |
10164 KB |
Output is correct |
9 |
Correct |
8 ms |
10268 KB |
Output is correct |
10 |
Correct |
6 ms |
9684 KB |
Output is correct |
11 |
Correct |
6 ms |
9764 KB |
Output is correct |
12 |
Correct |
122 ms |
26420 KB |
Output is correct |
13 |
Correct |
189 ms |
37440 KB |
Output is correct |
14 |
Correct |
184 ms |
34364 KB |
Output is correct |
15 |
Correct |
197 ms |
37068 KB |
Output is correct |
16 |
Correct |
211 ms |
37592 KB |
Output is correct |
17 |
Correct |
210 ms |
37392 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
175 ms |
34748 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
123 ms |
52212 KB |
Output is correct |
22 |
Correct |
144 ms |
57560 KB |
Output is correct |
23 |
Correct |
146 ms |
60928 KB |
Output is correct |
24 |
Correct |
154 ms |
60908 KB |
Output is correct |
25 |
Correct |
7 ms |
10580 KB |
Output is correct |
26 |
Correct |
8 ms |
10708 KB |
Output is correct |
27 |
Correct |
7 ms |
10628 KB |
Output is correct |
28 |
Correct |
5 ms |
9684 KB |
Output is correct |
29 |
Correct |
5 ms |
9684 KB |
Output is correct |
30 |
Correct |
5 ms |
9684 KB |
Output is correct |
31 |
Correct |
95 ms |
40360 KB |
Output is correct |
32 |
Correct |
155 ms |
60892 KB |
Output is correct |
33 |
Correct |
6 ms |
9684 KB |
Output is correct |
34 |
Correct |
132 ms |
55808 KB |
Output is correct |
35 |
Correct |
145 ms |
61048 KB |
Output is correct |
36 |
Correct |
5 ms |
9684 KB |
Output is correct |
37 |
Correct |
7 ms |
9684 KB |
Output is correct |
38 |
Correct |
5 ms |
9684 KB |
Output is correct |
39 |
Correct |
5 ms |
9684 KB |
Output is correct |
40 |
Correct |
5 ms |
9684 KB |
Output is correct |
41 |
Correct |
7 ms |
9760 KB |
Output is correct |
42 |
Correct |
5 ms |
9684 KB |
Output is correct |
43 |
Correct |
5 ms |
9684 KB |
Output is correct |
44 |
Correct |
6 ms |
9684 KB |
Output is correct |
45 |
Correct |
5 ms |
9792 KB |
Output is correct |
46 |
Correct |
5 ms |
9684 KB |
Output is correct |
47 |
Correct |
6 ms |
9684 KB |
Output is correct |
48 |
Correct |
5 ms |
9684 KB |
Output is correct |
49 |
Correct |
5 ms |
9760 KB |
Output is correct |
50 |
Correct |
5 ms |
9684 KB |
Output is correct |
51 |
Correct |
5 ms |
9664 KB |
Output is correct |
52 |
Correct |
5 ms |
9720 KB |
Output is correct |
53 |
Correct |
7 ms |
9696 KB |
Output is correct |
54 |
Correct |
6 ms |
9684 KB |
Output is correct |
55 |
Correct |
5 ms |
9684 KB |
Output is correct |
56 |
Correct |
5 ms |
9684 KB |
Output is correct |
57 |
Correct |
5 ms |
9612 KB |
Output is correct |
58 |
Correct |
8 ms |
9940 KB |
Output is correct |
59 |
Correct |
10 ms |
10188 KB |
Output is correct |
60 |
Correct |
8 ms |
10156 KB |
Output is correct |
61 |
Correct |
8 ms |
10196 KB |
Output is correct |
62 |
Correct |
8 ms |
10196 KB |
Output is correct |
63 |
Correct |
8 ms |
10196 KB |
Output is correct |
64 |
Correct |
7 ms |
10196 KB |
Output is correct |
65 |
Correct |
8 ms |
10196 KB |
Output is correct |
66 |
Correct |
7 ms |
10268 KB |
Output is correct |
67 |
Correct |
8 ms |
10196 KB |
Output is correct |
68 |
Correct |
7 ms |
10580 KB |
Output is correct |
69 |
Correct |
8 ms |
10708 KB |
Output is correct |
70 |
Correct |
7 ms |
10580 KB |
Output is correct |
71 |
Correct |
8 ms |
10196 KB |
Output is correct |
72 |
Correct |
9 ms |
10196 KB |
Output is correct |
73 |
Correct |
8 ms |
10296 KB |
Output is correct |
74 |
Correct |
5 ms |
9684 KB |
Output is correct |
75 |
Correct |
5 ms |
9684 KB |
Output is correct |
76 |
Correct |
6 ms |
9684 KB |
Output is correct |
77 |
Correct |
5 ms |
9684 KB |
Output is correct |
78 |
Correct |
5 ms |
9684 KB |
Output is correct |
79 |
Correct |
5 ms |
9684 KB |
Output is correct |
80 |
Correct |
5 ms |
9684 KB |
Output is correct |
81 |
Correct |
5 ms |
9684 KB |
Output is correct |
82 |
Correct |
5 ms |
9684 KB |
Output is correct |
83 |
Correct |
5 ms |
9684 KB |
Output is correct |
84 |
Correct |
5 ms |
9812 KB |
Output is correct |
85 |
Correct |
6 ms |
9684 KB |
Output is correct |
86 |
Correct |
7 ms |
9732 KB |
Output is correct |
87 |
Correct |
6 ms |
9684 KB |
Output is correct |
88 |
Correct |
7 ms |
9996 KB |
Output is correct |
89 |
Correct |
10 ms |
10128 KB |
Output is correct |
90 |
Correct |
10 ms |
10212 KB |
Output is correct |
91 |
Correct |
7 ms |
10068 KB |
Output is correct |
92 |
Correct |
7 ms |
10196 KB |
Output is correct |
93 |
Correct |
5 ms |
9684 KB |
Output is correct |
94 |
Correct |
5 ms |
9660 KB |
Output is correct |
95 |
Correct |
5 ms |
9684 KB |
Output is correct |
96 |
Correct |
5 ms |
9684 KB |
Output is correct |
97 |
Correct |
6 ms |
9684 KB |
Output is correct |
98 |
Correct |
5 ms |
9684 KB |
Output is correct |
99 |
Correct |
8 ms |
10196 KB |
Output is correct |
100 |
Correct |
8 ms |
10196 KB |
Output is correct |
101 |
Correct |
8 ms |
10196 KB |
Output is correct |
102 |
Correct |
8 ms |
10196 KB |
Output is correct |
103 |
Correct |
8 ms |
10196 KB |
Output is correct |
104 |
Correct |
206 ms |
37848 KB |
Output is correct |
105 |
Correct |
199 ms |
37480 KB |
Output is correct |
106 |
Correct |
193 ms |
39800 KB |
Output is correct |
107 |
Correct |
219 ms |
39820 KB |
Output is correct |
108 |
Correct |
184 ms |
37036 KB |
Output is correct |
109 |
Correct |
199 ms |
35120 KB |
Output is correct |
110 |
Correct |
187 ms |
36216 KB |
Output is correct |
111 |
Correct |
208 ms |
35456 KB |
Output is correct |
112 |
Correct |
185 ms |
42060 KB |
Output is correct |
113 |
Correct |
194 ms |
40428 KB |
Output is correct |
114 |
Correct |
194 ms |
39428 KB |
Output is correct |
115 |
Correct |
220 ms |
35184 KB |
Output is correct |
116 |
Correct |
5 ms |
9684 KB |
Output is correct |
117 |
Correct |
133 ms |
55844 KB |
Output is correct |
118 |
Correct |
142 ms |
60892 KB |
Output is correct |
119 |
Correct |
8 ms |
10140 KB |
Output is correct |
120 |
Correct |
7 ms |
10196 KB |
Output is correct |
121 |
Correct |
8 ms |
10196 KB |
Output is correct |
122 |
Correct |
8 ms |
10196 KB |
Output is correct |
123 |
Correct |
7 ms |
10196 KB |
Output is correct |
124 |
Correct |
175 ms |
34820 KB |
Output is correct |
125 |
Correct |
5 ms |
9684 KB |
Output is correct |
126 |
Correct |
5 ms |
9684 KB |
Output is correct |
127 |
Correct |
5 ms |
9684 KB |
Output is correct |
128 |
Correct |
170 ms |
34892 KB |
Output is correct |
129 |
Correct |
154 ms |
33536 KB |
Output is correct |
130 |
Correct |
205 ms |
40200 KB |
Output is correct |
131 |
Correct |
204 ms |
41420 KB |
Output is correct |
132 |
Correct |
171 ms |
36164 KB |
Output is correct |
133 |
Correct |
187 ms |
35488 KB |
Output is correct |
134 |
Correct |
206 ms |
35952 KB |
Output is correct |
135 |
Correct |
190 ms |
39780 KB |
Output is correct |
136 |
Correct |
200 ms |
37236 KB |
Output is correct |
137 |
Correct |
189 ms |
37608 KB |
Output is correct |
138 |
Correct |
198 ms |
44548 KB |
Output is correct |
139 |
Correct |
208 ms |
41548 KB |
Output is correct |
140 |
Correct |
209 ms |
34328 KB |
Output is correct |
141 |
Correct |
89 ms |
41228 KB |
Output is correct |
142 |
Correct |
146 ms |
62276 KB |
Output is correct |
143 |
Correct |
9 ms |
10068 KB |
Output is correct |
144 |
Correct |
8 ms |
10196 KB |
Output is correct |
145 |
Correct |
8 ms |
10196 KB |
Output is correct |
146 |
Correct |
7 ms |
10100 KB |
Output is correct |
147 |
Correct |
7 ms |
10196 KB |
Output is correct |
148 |
Correct |
5 ms |
9716 KB |
Output is correct |
149 |
Correct |
5 ms |
9684 KB |
Output is correct |
150 |
Correct |
6 ms |
9684 KB |
Output is correct |
151 |
Correct |
7 ms |
9684 KB |
Output is correct |
152 |
Correct |
5 ms |
9708 KB |
Output is correct |
153 |
Correct |
106 ms |
27028 KB |
Output is correct |
154 |
Correct |
194 ms |
38420 KB |
Output is correct |
155 |
Correct |
205 ms |
39132 KB |
Output is correct |
156 |
Correct |
196 ms |
38732 KB |
Output is correct |
157 |
Correct |
191 ms |
41200 KB |
Output is correct |
158 |
Correct |
215 ms |
41196 KB |
Output is correct |
159 |
Correct |
181 ms |
38548 KB |
Output is correct |
160 |
Correct |
193 ms |
36428 KB |
Output is correct |
161 |
Correct |
177 ms |
37620 KB |
Output is correct |
162 |
Correct |
203 ms |
36672 KB |
Output is correct |
163 |
Correct |
173 ms |
43264 KB |
Output is correct |
164 |
Correct |
193 ms |
41800 KB |
Output is correct |
165 |
Correct |
196 ms |
40524 KB |
Output is correct |
166 |
Correct |
204 ms |
36568 KB |
Output is correct |
167 |
Correct |
6 ms |
9704 KB |
Output is correct |
168 |
Correct |
127 ms |
57056 KB |
Output is correct |
169 |
Correct |
150 ms |
62388 KB |
Output is correct |
170 |
Correct |
8 ms |
10132 KB |
Output is correct |
171 |
Correct |
8 ms |
10196 KB |
Output is correct |
172 |
Correct |
8 ms |
10196 KB |
Output is correct |
173 |
Correct |
8 ms |
10228 KB |
Output is correct |
174 |
Correct |
8 ms |
10196 KB |
Output is correct |
175 |
Correct |
170 ms |
35732 KB |
Output is correct |
176 |
Correct |
5 ms |
9700 KB |
Output is correct |
177 |
Correct |
219 ms |
40976 KB |
Output is correct |
178 |
Correct |
154 ms |
33740 KB |
Output is correct |
179 |
Correct |
212 ms |
40788 KB |
Output is correct |
180 |
Correct |
202 ms |
37484 KB |
Output is correct |
181 |
Correct |
192 ms |
39372 KB |
Output is correct |
182 |
Correct |
210 ms |
38476 KB |
Output is correct |
183 |
Correct |
207 ms |
37760 KB |
Output is correct |
184 |
Correct |
192 ms |
36272 KB |
Output is correct |
185 |
Correct |
199 ms |
36028 KB |
Output is correct |
186 |
Correct |
203 ms |
34844 KB |
Output is correct |
187 |
Correct |
217 ms |
39284 KB |
Output is correct |
188 |
Correct |
201 ms |
39620 KB |
Output is correct |
189 |
Correct |
203 ms |
41208 KB |
Output is correct |
190 |
Correct |
215 ms |
40780 KB |
Output is correct |
191 |
Correct |
211 ms |
40680 KB |
Output is correct |
192 |
Correct |
219 ms |
36308 KB |
Output is correct |
193 |
Correct |
219 ms |
36672 KB |
Output is correct |
194 |
Correct |
195 ms |
41068 KB |
Output is correct |
195 |
Correct |
124 ms |
54060 KB |
Output is correct |
196 |
Correct |
138 ms |
59664 KB |
Output is correct |
197 |
Correct |
146 ms |
63080 KB |
Output is correct |
198 |
Correct |
148 ms |
63096 KB |
Output is correct |
199 |
Correct |
7 ms |
9948 KB |
Output is correct |
200 |
Correct |
7 ms |
10272 KB |
Output is correct |
201 |
Correct |
8 ms |
10196 KB |
Output is correct |
202 |
Correct |
8 ms |
10196 KB |
Output is correct |
203 |
Correct |
8 ms |
10228 KB |
Output is correct |
204 |
Correct |
9 ms |
10196 KB |
Output is correct |
205 |
Correct |
8 ms |
10196 KB |
Output is correct |
206 |
Correct |
8 ms |
10196 KB |
Output is correct |
207 |
Correct |
8 ms |
10280 KB |
Output is correct |
208 |
Correct |
8 ms |
10196 KB |
Output is correct |
209 |
Correct |
7 ms |
10608 KB |
Output is correct |
210 |
Correct |
7 ms |
10736 KB |
Output is correct |
211 |
Correct |
7 ms |
10580 KB |
Output is correct |
212 |
Correct |
7 ms |
10228 KB |
Output is correct |
213 |
Correct |
8 ms |
10324 KB |
Output is correct |
214 |
Correct |
8 ms |
10292 KB |
Output is correct |
215 |
Correct |
6 ms |
9704 KB |
Output is correct |
216 |
Correct |
5 ms |
9628 KB |
Output is correct |
217 |
Correct |
5 ms |
9704 KB |
Output is correct |
218 |
Correct |
5 ms |
9684 KB |
Output is correct |
219 |
Correct |
5 ms |
9684 KB |
Output is correct |
220 |
Correct |
5 ms |
9744 KB |
Output is correct |
221 |
Correct |
5 ms |
9684 KB |
Output is correct |
222 |
Correct |
6 ms |
9684 KB |
Output is correct |
223 |
Correct |
6 ms |
9696 KB |
Output is correct |
224 |
Correct |
7 ms |
9684 KB |
Output is correct |
225 |
Correct |
7 ms |
9812 KB |
Output is correct |
226 |
Correct |
5 ms |
9684 KB |
Output is correct |
227 |
Correct |
6 ms |
9684 KB |
Output is correct |
228 |
Correct |
6 ms |
9684 KB |
Output is correct |
229 |
Correct |
178 ms |
36140 KB |
Output is correct |
230 |
Correct |
155 ms |
33384 KB |
Output is correct |
231 |
Correct |
205 ms |
40176 KB |
Output is correct |
232 |
Correct |
211 ms |
41552 KB |
Output is correct |
233 |
Correct |
171 ms |
36100 KB |
Output is correct |
234 |
Correct |
187 ms |
35396 KB |
Output is correct |
235 |
Correct |
238 ms |
35952 KB |
Output is correct |
236 |
Correct |
185 ms |
39656 KB |
Output is correct |
237 |
Correct |
200 ms |
37252 KB |
Output is correct |
238 |
Correct |
200 ms |
37664 KB |
Output is correct |
239 |
Correct |
196 ms |
44492 KB |
Output is correct |
240 |
Correct |
215 ms |
41584 KB |
Output is correct |
241 |
Correct |
217 ms |
34336 KB |
Output is correct |
242 |
Correct |
85 ms |
41120 KB |
Output is correct |
243 |
Correct |
146 ms |
62196 KB |
Output is correct |
244 |
Correct |
7 ms |
10068 KB |
Output is correct |
245 |
Correct |
7 ms |
10196 KB |
Output is correct |
246 |
Correct |
8 ms |
10196 KB |
Output is correct |
247 |
Correct |
8 ms |
10200 KB |
Output is correct |
248 |
Correct |
7 ms |
10196 KB |
Output is correct |
249 |
Correct |
6 ms |
9684 KB |
Output is correct |
250 |
Correct |
5 ms |
9684 KB |
Output is correct |
251 |
Correct |
5 ms |
9700 KB |
Output is correct |
252 |
Correct |
5 ms |
9684 KB |
Output is correct |
253 |
Correct |
6 ms |
9704 KB |
Output is correct |
254 |
Correct |
109 ms |
27028 KB |
Output is correct |
255 |
Correct |
186 ms |
38472 KB |
Output is correct |
256 |
Correct |
182 ms |
35956 KB |
Output is correct |
257 |
Correct |
202 ms |
38716 KB |
Output is correct |
258 |
Correct |
200 ms |
39128 KB |
Output is correct |
259 |
Correct |
206 ms |
39356 KB |
Output is correct |
260 |
Correct |
191 ms |
39144 KB |
Output is correct |
261 |
Correct |
190 ms |
38708 KB |
Output is correct |
262 |
Correct |
195 ms |
41196 KB |
Output is correct |
263 |
Correct |
204 ms |
41208 KB |
Output is correct |
264 |
Correct |
185 ms |
38416 KB |
Output is correct |
265 |
Correct |
185 ms |
36556 KB |
Output is correct |
266 |
Correct |
189 ms |
37596 KB |
Output is correct |
267 |
Correct |
192 ms |
36540 KB |
Output is correct |
268 |
Correct |
174 ms |
43340 KB |
Output is correct |
269 |
Correct |
193 ms |
41796 KB |
Output is correct |
270 |
Correct |
190 ms |
40640 KB |
Output is correct |
271 |
Correct |
210 ms |
36696 KB |
Output is correct |
272 |
Correct |
5 ms |
9624 KB |
Output is correct |
273 |
Correct |
126 ms |
57088 KB |
Output is correct |
274 |
Correct |
142 ms |
62272 KB |
Output is correct |
275 |
Correct |
7 ms |
10196 KB |
Output is correct |
276 |
Correct |
8 ms |
10324 KB |
Output is correct |
277 |
Correct |
7 ms |
10224 KB |
Output is correct |
278 |
Correct |
8 ms |
10196 KB |
Output is correct |
279 |
Correct |
7 ms |
10260 KB |
Output is correct |
280 |
Correct |
183 ms |
35732 KB |
Output is correct |