#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)
{
if(lo.empty() || lo.size() && ct.back().se>*lo.rbegin())
{
hi.insert(ct.back().se);
del+=ct.back().se;
}
else lo.insert(ct.back().se);
ct.pop_back();
}
}
/*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)
| ~~~~~~~~~~~~~~~~~~~~~~~^~~
roads.cpp:144:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
144 | if(lo.empty() || lo.size() && ct.back().se>*lo.rbegin())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
8 ms |
10268 KB |
Output is correct |
3 |
Correct |
8 ms |
10196 KB |
Output is correct |
4 |
Correct |
7 ms |
10196 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
7 ms |
10196 KB |
Output is correct |
9 |
Correct |
7 ms |
10196 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
111 ms |
26372 KB |
Output is correct |
13 |
Correct |
194 ms |
37436 KB |
Output is correct |
14 |
Correct |
177 ms |
34492 KB |
Output is correct |
15 |
Correct |
227 ms |
37188 KB |
Output is correct |
16 |
Correct |
204 ms |
37436 KB |
Output is correct |
17 |
Correct |
203 ms |
37552 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
175 ms |
34856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
124 ms |
52248 KB |
Output is correct |
3 |
Correct |
142 ms |
57628 KB |
Output is correct |
4 |
Correct |
149 ms |
60992 KB |
Output is correct |
5 |
Correct |
144 ms |
60884 KB |
Output is correct |
6 |
Correct |
8 ms |
10568 KB |
Output is correct |
7 |
Correct |
10 ms |
10708 KB |
Output is correct |
8 |
Correct |
9 ms |
10580 KB |
Output is correct |
9 |
Correct |
6 ms |
9784 KB |
Output is correct |
10 |
Correct |
5 ms |
9800 KB |
Output is correct |
11 |
Correct |
5 ms |
9816 KB |
Output is correct |
12 |
Correct |
85 ms |
40400 KB |
Output is correct |
13 |
Correct |
140 ms |
60848 KB |
Output is correct |
14 |
Correct |
5 ms |
9692 KB |
Output is correct |
15 |
Correct |
126 ms |
55828 KB |
Output is correct |
16 |
Correct |
192 ms |
60932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9668 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9684 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 |
9716 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9800 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9688 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9668 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9684 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 |
9716 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9800 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9688 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
9684 KB |
Output is correct |
22 |
Correct |
5 ms |
9684 KB |
Output is correct |
23 |
Correct |
8 ms |
9940 KB |
Output is correct |
24 |
Correct |
7 ms |
10196 KB |
Output is correct |
25 |
Correct |
7 ms |
10068 KB |
Output is correct |
26 |
Correct |
8 ms |
10196 KB |
Output is correct |
27 |
Correct |
8 ms |
10196 KB |
Output is correct |
28 |
Correct |
9 ms |
10196 KB |
Output is correct |
29 |
Correct |
7 ms |
10196 KB |
Output is correct |
30 |
Correct |
9 ms |
10188 KB |
Output is correct |
31 |
Correct |
12 ms |
10172 KB |
Output is correct |
32 |
Correct |
8 ms |
10196 KB |
Output is correct |
33 |
Correct |
8 ms |
10572 KB |
Output is correct |
34 |
Correct |
8 ms |
10664 KB |
Output is correct |
35 |
Correct |
8 ms |
10620 KB |
Output is correct |
36 |
Correct |
9 ms |
10196 KB |
Output is correct |
37 |
Correct |
7 ms |
10196 KB |
Output is correct |
38 |
Correct |
8 ms |
10236 KB |
Output is correct |
39 |
Correct |
5 ms |
9684 KB |
Output is correct |
40 |
Correct |
5 ms |
9684 KB |
Output is correct |
41 |
Correct |
5 ms |
9684 KB |
Output is correct |
42 |
Correct |
6 ms |
9756 KB |
Output is correct |
43 |
Correct |
5 ms |
9684 KB |
Output is correct |
44 |
Correct |
5 ms |
9684 KB |
Output is correct |
45 |
Correct |
6 ms |
9760 KB |
Output is correct |
46 |
Correct |
6 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 |
6 ms |
9684 KB |
Output is correct |
50 |
Correct |
6 ms |
9748 KB |
Output is correct |
51 |
Correct |
6 ms |
9764 KB |
Output is correct |
52 |
Correct |
6 ms |
9760 KB |
Output is correct |
53 |
Correct |
7 ms |
10068 KB |
Output is correct |
54 |
Correct |
8 ms |
10240 KB |
Output is correct |
55 |
Correct |
8 ms |
10232 KB |
Output is correct |
56 |
Correct |
7 ms |
10124 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 |
9684 KB |
Output is correct |
60 |
Correct |
5 ms |
9684 KB |
Output is correct |
61 |
Correct |
6 ms |
9760 KB |
Output is correct |
62 |
Correct |
6 ms |
9768 KB |
Output is correct |
63 |
Correct |
6 ms |
9684 KB |
Output is correct |
64 |
Correct |
8 ms |
10196 KB |
Output is correct |
65 |
Correct |
10 ms |
10212 KB |
Output is correct |
66 |
Correct |
8 ms |
10252 KB |
Output is correct |
67 |
Correct |
8 ms |
10196 KB |
Output is correct |
68 |
Correct |
7 ms |
10196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
194 ms |
37780 KB |
Output is correct |
2 |
Correct |
192 ms |
37324 KB |
Output is correct |
3 |
Correct |
199 ms |
39796 KB |
Output is correct |
4 |
Correct |
207 ms |
39804 KB |
Output is correct |
5 |
Correct |
181 ms |
37248 KB |
Output is correct |
6 |
Correct |
210 ms |
35148 KB |
Output is correct |
7 |
Correct |
188 ms |
36212 KB |
Output is correct |
8 |
Correct |
198 ms |
35380 KB |
Output is correct |
9 |
Correct |
174 ms |
42036 KB |
Output is correct |
10 |
Correct |
200 ms |
40396 KB |
Output is correct |
11 |
Correct |
216 ms |
39340 KB |
Output is correct |
12 |
Correct |
206 ms |
35180 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
128 ms |
55796 KB |
Output is correct |
15 |
Correct |
150 ms |
60932 KB |
Output is correct |
16 |
Correct |
8 ms |
10196 KB |
Output is correct |
17 |
Correct |
8 ms |
10212 KB |
Output is correct |
18 |
Correct |
8 ms |
10236 KB |
Output is correct |
19 |
Correct |
9 ms |
10096 KB |
Output is correct |
20 |
Correct |
9 ms |
10240 KB |
Output is correct |
21 |
Correct |
188 ms |
34820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
194 ms |
37780 KB |
Output is correct |
2 |
Correct |
192 ms |
37324 KB |
Output is correct |
3 |
Correct |
199 ms |
39796 KB |
Output is correct |
4 |
Correct |
207 ms |
39804 KB |
Output is correct |
5 |
Correct |
181 ms |
37248 KB |
Output is correct |
6 |
Correct |
210 ms |
35148 KB |
Output is correct |
7 |
Correct |
188 ms |
36212 KB |
Output is correct |
8 |
Correct |
198 ms |
35380 KB |
Output is correct |
9 |
Correct |
174 ms |
42036 KB |
Output is correct |
10 |
Correct |
200 ms |
40396 KB |
Output is correct |
11 |
Correct |
216 ms |
39340 KB |
Output is correct |
12 |
Correct |
206 ms |
35180 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
128 ms |
55796 KB |
Output is correct |
15 |
Correct |
150 ms |
60932 KB |
Output is correct |
16 |
Correct |
8 ms |
10196 KB |
Output is correct |
17 |
Correct |
8 ms |
10212 KB |
Output is correct |
18 |
Correct |
8 ms |
10236 KB |
Output is correct |
19 |
Correct |
9 ms |
10096 KB |
Output is correct |
20 |
Correct |
9 ms |
10240 KB |
Output is correct |
21 |
Correct |
188 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 |
179 ms |
34792 KB |
Output is correct |
26 |
Correct |
175 ms |
32460 KB |
Output is correct |
27 |
Correct |
198 ms |
38732 KB |
Output is correct |
28 |
Correct |
215 ms |
40072 KB |
Output is correct |
29 |
Correct |
203 ms |
34956 KB |
Output is correct |
30 |
Correct |
190 ms |
34104 KB |
Output is correct |
31 |
Correct |
254 ms |
34540 KB |
Output is correct |
32 |
Correct |
200 ms |
38372 KB |
Output is correct |
33 |
Correct |
194 ms |
35956 KB |
Output is correct |
34 |
Correct |
237 ms |
36284 KB |
Output is correct |
35 |
Correct |
231 ms |
43080 KB |
Output is correct |
36 |
Correct |
221 ms |
40272 KB |
Output is correct |
37 |
Correct |
214 ms |
32920 KB |
Output is correct |
38 |
Correct |
86 ms |
40384 KB |
Output is correct |
39 |
Correct |
145 ms |
60912 KB |
Output is correct |
40 |
Correct |
7 ms |
10068 KB |
Output is correct |
41 |
Correct |
9 ms |
10196 KB |
Output is correct |
42 |
Correct |
10 ms |
10196 KB |
Output is correct |
43 |
Correct |
9 ms |
10144 KB |
Output is correct |
44 |
Correct |
9 ms |
10268 KB |
Output is correct |
45 |
Correct |
6 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 |
9684 KB |
Output is correct |
50 |
Correct |
123 ms |
26364 KB |
Output is correct |
51 |
Correct |
230 ms |
37496 KB |
Output is correct |
52 |
Correct |
199 ms |
37876 KB |
Output is correct |
53 |
Correct |
206 ms |
37360 KB |
Output is correct |
54 |
Correct |
208 ms |
39804 KB |
Output is correct |
55 |
Correct |
206 ms |
39920 KB |
Output is correct |
56 |
Correct |
179 ms |
37068 KB |
Output is correct |
57 |
Correct |
223 ms |
35064 KB |
Output is correct |
58 |
Correct |
195 ms |
36212 KB |
Output is correct |
59 |
Correct |
193 ms |
35336 KB |
Output is correct |
60 |
Correct |
205 ms |
42096 KB |
Output is correct |
61 |
Correct |
208 ms |
40396 KB |
Output is correct |
62 |
Correct |
204 ms |
39244 KB |
Output is correct |
63 |
Correct |
226 ms |
35200 KB |
Output is correct |
64 |
Correct |
5 ms |
9684 KB |
Output is correct |
65 |
Correct |
149 ms |
55772 KB |
Output is correct |
66 |
Correct |
149 ms |
60932 KB |
Output is correct |
67 |
Correct |
8 ms |
10196 KB |
Output is correct |
68 |
Correct |
8 ms |
10196 KB |
Output is correct |
69 |
Correct |
8 ms |
10196 KB |
Output is correct |
70 |
Correct |
7 ms |
10196 KB |
Output is correct |
71 |
Correct |
8 ms |
10196 KB |
Output is correct |
72 |
Correct |
174 ms |
34848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
8 ms |
10268 KB |
Output is correct |
3 |
Correct |
8 ms |
10196 KB |
Output is correct |
4 |
Correct |
7 ms |
10196 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
7 ms |
10196 KB |
Output is correct |
9 |
Correct |
7 ms |
10196 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
111 ms |
26372 KB |
Output is correct |
13 |
Correct |
194 ms |
37436 KB |
Output is correct |
14 |
Correct |
177 ms |
34492 KB |
Output is correct |
15 |
Correct |
227 ms |
37188 KB |
Output is correct |
16 |
Correct |
204 ms |
37436 KB |
Output is correct |
17 |
Correct |
203 ms |
37552 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
175 ms |
34856 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
124 ms |
52248 KB |
Output is correct |
22 |
Correct |
142 ms |
57628 KB |
Output is correct |
23 |
Correct |
149 ms |
60992 KB |
Output is correct |
24 |
Correct |
144 ms |
60884 KB |
Output is correct |
25 |
Correct |
8 ms |
10568 KB |
Output is correct |
26 |
Correct |
10 ms |
10708 KB |
Output is correct |
27 |
Correct |
9 ms |
10580 KB |
Output is correct |
28 |
Correct |
6 ms |
9784 KB |
Output is correct |
29 |
Correct |
5 ms |
9800 KB |
Output is correct |
30 |
Correct |
5 ms |
9816 KB |
Output is correct |
31 |
Correct |
85 ms |
40400 KB |
Output is correct |
32 |
Correct |
140 ms |
60848 KB |
Output is correct |
33 |
Correct |
5 ms |
9692 KB |
Output is correct |
34 |
Correct |
126 ms |
55828 KB |
Output is correct |
35 |
Correct |
192 ms |
60932 KB |
Output is correct |
36 |
Correct |
6 ms |
9684 KB |
Output is correct |
37 |
Correct |
5 ms |
9684 KB |
Output is correct |
38 |
Correct |
5 ms |
9684 KB |
Output is correct |
39 |
Correct |
5 ms |
9668 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 |
6 ms |
9716 KB |
Output is correct |
45 |
Correct |
5 ms |
9684 KB |
Output is correct |
46 |
Correct |
5 ms |
9800 KB |
Output is correct |
47 |
Correct |
6 ms |
9684 KB |
Output is correct |
48 |
Correct |
5 ms |
9684 KB |
Output is correct |
49 |
Correct |
6 ms |
9688 KB |
Output is correct |
50 |
Correct |
5 ms |
9684 KB |
Output is correct |
51 |
Correct |
5 ms |
9684 KB |
Output is correct |
52 |
Correct |
5 ms |
9684 KB |
Output is correct |
53 |
Correct |
5 ms |
9684 KB |
Output is correct |
54 |
Correct |
6 ms |
9684 KB |
Output is correct |
55 |
Correct |
6 ms |
9684 KB |
Output is correct |
56 |
Correct |
6 ms |
9684 KB |
Output is correct |
57 |
Correct |
5 ms |
9684 KB |
Output is correct |
58 |
Correct |
8 ms |
9940 KB |
Output is correct |
59 |
Correct |
7 ms |
10196 KB |
Output is correct |
60 |
Correct |
7 ms |
10068 KB |
Output is correct |
61 |
Correct |
8 ms |
10196 KB |
Output is correct |
62 |
Correct |
8 ms |
10196 KB |
Output is correct |
63 |
Correct |
9 ms |
10196 KB |
Output is correct |
64 |
Correct |
7 ms |
10196 KB |
Output is correct |
65 |
Correct |
9 ms |
10188 KB |
Output is correct |
66 |
Correct |
12 ms |
10172 KB |
Output is correct |
67 |
Correct |
8 ms |
10196 KB |
Output is correct |
68 |
Correct |
8 ms |
10572 KB |
Output is correct |
69 |
Correct |
8 ms |
10664 KB |
Output is correct |
70 |
Correct |
8 ms |
10620 KB |
Output is correct |
71 |
Correct |
9 ms |
10196 KB |
Output is correct |
72 |
Correct |
7 ms |
10196 KB |
Output is correct |
73 |
Correct |
8 ms |
10236 KB |
Output is correct |
74 |
Correct |
5 ms |
9684 KB |
Output is correct |
75 |
Correct |
5 ms |
9684 KB |
Output is correct |
76 |
Correct |
5 ms |
9684 KB |
Output is correct |
77 |
Correct |
6 ms |
9756 KB |
Output is correct |
78 |
Correct |
5 ms |
9684 KB |
Output is correct |
79 |
Correct |
5 ms |
9684 KB |
Output is correct |
80 |
Correct |
6 ms |
9760 KB |
Output is correct |
81 |
Correct |
6 ms |
9684 KB |
Output is correct |
82 |
Correct |
6 ms |
9684 KB |
Output is correct |
83 |
Correct |
7 ms |
9684 KB |
Output is correct |
84 |
Correct |
6 ms |
9684 KB |
Output is correct |
85 |
Correct |
6 ms |
9748 KB |
Output is correct |
86 |
Correct |
6 ms |
9764 KB |
Output is correct |
87 |
Correct |
6 ms |
9760 KB |
Output is correct |
88 |
Correct |
7 ms |
10068 KB |
Output is correct |
89 |
Correct |
8 ms |
10240 KB |
Output is correct |
90 |
Correct |
8 ms |
10232 KB |
Output is correct |
91 |
Correct |
7 ms |
10124 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 |
9684 KB |
Output is correct |
95 |
Correct |
5 ms |
9684 KB |
Output is correct |
96 |
Correct |
6 ms |
9760 KB |
Output is correct |
97 |
Correct |
6 ms |
9768 KB |
Output is correct |
98 |
Correct |
6 ms |
9684 KB |
Output is correct |
99 |
Correct |
8 ms |
10196 KB |
Output is correct |
100 |
Correct |
10 ms |
10212 KB |
Output is correct |
101 |
Correct |
8 ms |
10252 KB |
Output is correct |
102 |
Correct |
8 ms |
10196 KB |
Output is correct |
103 |
Correct |
7 ms |
10196 KB |
Output is correct |
104 |
Correct |
194 ms |
37780 KB |
Output is correct |
105 |
Correct |
192 ms |
37324 KB |
Output is correct |
106 |
Correct |
199 ms |
39796 KB |
Output is correct |
107 |
Correct |
207 ms |
39804 KB |
Output is correct |
108 |
Correct |
181 ms |
37248 KB |
Output is correct |
109 |
Correct |
210 ms |
35148 KB |
Output is correct |
110 |
Correct |
188 ms |
36212 KB |
Output is correct |
111 |
Correct |
198 ms |
35380 KB |
Output is correct |
112 |
Correct |
174 ms |
42036 KB |
Output is correct |
113 |
Correct |
200 ms |
40396 KB |
Output is correct |
114 |
Correct |
216 ms |
39340 KB |
Output is correct |
115 |
Correct |
206 ms |
35180 KB |
Output is correct |
116 |
Correct |
5 ms |
9684 KB |
Output is correct |
117 |
Correct |
128 ms |
55796 KB |
Output is correct |
118 |
Correct |
150 ms |
60932 KB |
Output is correct |
119 |
Correct |
8 ms |
10196 KB |
Output is correct |
120 |
Correct |
8 ms |
10212 KB |
Output is correct |
121 |
Correct |
8 ms |
10236 KB |
Output is correct |
122 |
Correct |
9 ms |
10096 KB |
Output is correct |
123 |
Correct |
9 ms |
10240 KB |
Output is correct |
124 |
Correct |
188 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 |
179 ms |
34792 KB |
Output is correct |
129 |
Correct |
175 ms |
32460 KB |
Output is correct |
130 |
Correct |
198 ms |
38732 KB |
Output is correct |
131 |
Correct |
215 ms |
40072 KB |
Output is correct |
132 |
Correct |
203 ms |
34956 KB |
Output is correct |
133 |
Correct |
190 ms |
34104 KB |
Output is correct |
134 |
Correct |
254 ms |
34540 KB |
Output is correct |
135 |
Correct |
200 ms |
38372 KB |
Output is correct |
136 |
Correct |
194 ms |
35956 KB |
Output is correct |
137 |
Correct |
237 ms |
36284 KB |
Output is correct |
138 |
Correct |
231 ms |
43080 KB |
Output is correct |
139 |
Correct |
221 ms |
40272 KB |
Output is correct |
140 |
Correct |
214 ms |
32920 KB |
Output is correct |
141 |
Correct |
86 ms |
40384 KB |
Output is correct |
142 |
Correct |
145 ms |
60912 KB |
Output is correct |
143 |
Correct |
7 ms |
10068 KB |
Output is correct |
144 |
Correct |
9 ms |
10196 KB |
Output is correct |
145 |
Correct |
10 ms |
10196 KB |
Output is correct |
146 |
Correct |
9 ms |
10144 KB |
Output is correct |
147 |
Correct |
9 ms |
10268 KB |
Output is correct |
148 |
Correct |
6 ms |
9684 KB |
Output is correct |
149 |
Correct |
5 ms |
9684 KB |
Output is correct |
150 |
Correct |
5 ms |
9684 KB |
Output is correct |
151 |
Correct |
5 ms |
9684 KB |
Output is correct |
152 |
Correct |
5 ms |
9684 KB |
Output is correct |
153 |
Correct |
123 ms |
26364 KB |
Output is correct |
154 |
Correct |
230 ms |
37496 KB |
Output is correct |
155 |
Correct |
199 ms |
37876 KB |
Output is correct |
156 |
Correct |
206 ms |
37360 KB |
Output is correct |
157 |
Correct |
208 ms |
39804 KB |
Output is correct |
158 |
Correct |
206 ms |
39920 KB |
Output is correct |
159 |
Correct |
179 ms |
37068 KB |
Output is correct |
160 |
Correct |
223 ms |
35064 KB |
Output is correct |
161 |
Correct |
195 ms |
36212 KB |
Output is correct |
162 |
Correct |
193 ms |
35336 KB |
Output is correct |
163 |
Correct |
205 ms |
42096 KB |
Output is correct |
164 |
Correct |
208 ms |
40396 KB |
Output is correct |
165 |
Correct |
204 ms |
39244 KB |
Output is correct |
166 |
Correct |
226 ms |
35200 KB |
Output is correct |
167 |
Correct |
5 ms |
9684 KB |
Output is correct |
168 |
Correct |
149 ms |
55772 KB |
Output is correct |
169 |
Correct |
149 ms |
60932 KB |
Output is correct |
170 |
Correct |
8 ms |
10196 KB |
Output is correct |
171 |
Correct |
8 ms |
10196 KB |
Output is correct |
172 |
Correct |
8 ms |
10196 KB |
Output is correct |
173 |
Correct |
7 ms |
10196 KB |
Output is correct |
174 |
Correct |
8 ms |
10196 KB |
Output is correct |
175 |
Correct |
174 ms |
34848 KB |
Output is correct |
176 |
Correct |
6 ms |
9684 KB |
Output is correct |
177 |
Correct |
245 ms |
38888 KB |
Output is correct |
178 |
Correct |
169 ms |
32116 KB |
Output is correct |
179 |
Correct |
226 ms |
39532 KB |
Output is correct |
180 |
Correct |
220 ms |
35388 KB |
Output is correct |
181 |
Correct |
187 ms |
37152 KB |
Output is correct |
182 |
Correct |
209 ms |
36912 KB |
Output is correct |
183 |
Correct |
228 ms |
36196 KB |
Output is correct |
184 |
Correct |
192 ms |
34320 KB |
Output is correct |
185 |
Correct |
214 ms |
33948 KB |
Output is correct |
186 |
Correct |
250 ms |
32708 KB |
Output is correct |
187 |
Correct |
240 ms |
37184 KB |
Output is correct |
188 |
Correct |
212 ms |
38264 KB |
Output is correct |
189 |
Correct |
238 ms |
39196 KB |
Output is correct |
190 |
Correct |
227 ms |
38660 KB |
Output is correct |
191 |
Correct |
279 ms |
39312 KB |
Output is correct |
192 |
Correct |
257 ms |
34012 KB |
Output is correct |
193 |
Correct |
247 ms |
34500 KB |
Output is correct |
194 |
Correct |
210 ms |
38904 KB |
Output is correct |
195 |
Correct |
126 ms |
52148 KB |
Output is correct |
196 |
Correct |
140 ms |
57656 KB |
Output is correct |
197 |
Correct |
151 ms |
60956 KB |
Output is correct |
198 |
Correct |
165 ms |
61020 KB |
Output is correct |
199 |
Correct |
7 ms |
9964 KB |
Output is correct |
200 |
Correct |
9 ms |
10236 KB |
Output is correct |
201 |
Correct |
7 ms |
10068 KB |
Output is correct |
202 |
Correct |
10 ms |
10188 KB |
Output is correct |
203 |
Correct |
9 ms |
10196 KB |
Output is correct |
204 |
Correct |
8 ms |
10196 KB |
Output is correct |
205 |
Correct |
9 ms |
10184 KB |
Output is correct |
206 |
Correct |
9 ms |
10196 KB |
Output is correct |
207 |
Correct |
8 ms |
10204 KB |
Output is correct |
208 |
Correct |
10 ms |
10196 KB |
Output is correct |
209 |
Correct |
8 ms |
10528 KB |
Output is correct |
210 |
Correct |
8 ms |
10708 KB |
Output is correct |
211 |
Correct |
8 ms |
10624 KB |
Output is correct |
212 |
Correct |
9 ms |
10196 KB |
Output is correct |
213 |
Correct |
9 ms |
10196 KB |
Output is correct |
214 |
Correct |
8 ms |
10196 KB |
Output is correct |
215 |
Correct |
5 ms |
9684 KB |
Output is correct |
216 |
Correct |
5 ms |
9692 KB |
Output is correct |
217 |
Correct |
5 ms |
9684 KB |
Output is correct |
218 |
Correct |
6 ms |
9684 KB |
Output is correct |
219 |
Correct |
7 ms |
9684 KB |
Output is correct |
220 |
Correct |
6 ms |
9684 KB |
Output is correct |
221 |
Correct |
6 ms |
9712 KB |
Output is correct |
222 |
Correct |
7 ms |
9668 KB |
Output is correct |
223 |
Correct |
6 ms |
9684 KB |
Output is correct |
224 |
Correct |
5 ms |
9684 KB |
Output is correct |
225 |
Correct |
5 ms |
9812 KB |
Output is correct |
226 |
Correct |
6 ms |
9684 KB |
Output is correct |
227 |
Correct |
5 ms |
9684 KB |
Output is correct |
228 |
Correct |
5 ms |
9684 KB |
Output is correct |
229 |
Correct |
171 ms |
34904 KB |
Output is correct |
230 |
Correct |
176 ms |
32384 KB |
Output is correct |
231 |
Correct |
218 ms |
38772 KB |
Output is correct |
232 |
Correct |
211 ms |
40192 KB |
Output is correct |
233 |
Correct |
187 ms |
34836 KB |
Output is correct |
234 |
Correct |
188 ms |
34124 KB |
Output is correct |
235 |
Correct |
218 ms |
34560 KB |
Output is correct |
236 |
Correct |
193 ms |
38400 KB |
Output is correct |
237 |
Correct |
188 ms |
35940 KB |
Output is correct |
238 |
Correct |
232 ms |
36284 KB |
Output is correct |
239 |
Correct |
218 ms |
43128 KB |
Output is correct |
240 |
Correct |
227 ms |
40220 KB |
Output is correct |
241 |
Correct |
231 ms |
33156 KB |
Output is correct |
242 |
Correct |
90 ms |
40428 KB |
Output is correct |
243 |
Correct |
146 ms |
60908 KB |
Output is correct |
244 |
Correct |
8 ms |
10068 KB |
Output is correct |
245 |
Correct |
10 ms |
10208 KB |
Output is correct |
246 |
Correct |
12 ms |
10204 KB |
Output is correct |
247 |
Correct |
9 ms |
10116 KB |
Output is correct |
248 |
Correct |
7 ms |
10196 KB |
Output is correct |
249 |
Correct |
5 ms |
9684 KB |
Output is correct |
250 |
Correct |
5 ms |
9756 KB |
Output is correct |
251 |
Correct |
5 ms |
9684 KB |
Output is correct |
252 |
Correct |
6 ms |
9640 KB |
Output is correct |
253 |
Correct |
6 ms |
9684 KB |
Output is correct |
254 |
Correct |
110 ms |
26536 KB |
Output is correct |
255 |
Correct |
204 ms |
37412 KB |
Output is correct |
256 |
Correct |
218 ms |
34412 KB |
Output is correct |
257 |
Correct |
221 ms |
37092 KB |
Output is correct |
258 |
Correct |
232 ms |
37488 KB |
Output is correct |
259 |
Correct |
228 ms |
37576 KB |
Output is correct |
260 |
Correct |
229 ms |
37836 KB |
Output is correct |
261 |
Correct |
198 ms |
37316 KB |
Output is correct |
262 |
Correct |
200 ms |
39864 KB |
Output is correct |
263 |
Correct |
218 ms |
39836 KB |
Output is correct |
264 |
Correct |
184 ms |
37068 KB |
Output is correct |
265 |
Correct |
207 ms |
35148 KB |
Output is correct |
266 |
Correct |
225 ms |
36172 KB |
Output is correct |
267 |
Correct |
202 ms |
35340 KB |
Output is correct |
268 |
Correct |
184 ms |
42124 KB |
Output is correct |
269 |
Correct |
201 ms |
40604 KB |
Output is correct |
270 |
Correct |
201 ms |
39292 KB |
Output is correct |
271 |
Correct |
224 ms |
35188 KB |
Output is correct |
272 |
Correct |
5 ms |
9684 KB |
Output is correct |
273 |
Correct |
143 ms |
55860 KB |
Output is correct |
274 |
Correct |
151 ms |
60860 KB |
Output is correct |
275 |
Correct |
8 ms |
10196 KB |
Output is correct |
276 |
Correct |
8 ms |
10196 KB |
Output is correct |
277 |
Correct |
9 ms |
10196 KB |
Output is correct |
278 |
Correct |
7 ms |
10196 KB |
Output is correct |
279 |
Correct |
9 ms |
10148 KB |
Output is correct |
280 |
Correct |
179 ms |
34828 KB |
Output is correct |