#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N;
vector<pii> adj[MAXN+10], adj2[MAXN+10];
int par[MAXN+10], val[MAXN+10], sz[MAXN+10], deg[MAXN+10], dfn[MAXN+10];
ll ans[MAXN+10];
struct Edge
{
int u, v, w, p;
};
Edge E[MAXN+10];
int K;
int cnt;
ll dp1[MAXN+10], dp2[MAXN+10];
void dfs(int now, int bef)
{
sz[now]=1;
dfn[now]=++cnt;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
par[nxt.first]=now;
val[nxt.first]=nxt.second;
sz[now]+=sz[nxt.first];
dfs(nxt.first, now);
dp1[now]+=dp2[nxt.first];
}
dp2[now]=dp1[now]+E[val[now]].w;
}
struct Node
{
ll sum, cnt;
Node *lc, *rc;
Node() : sum(0), cnt(0), lc(NULL), rc(NULL) {}
};
struct SEG
{
Node *root;
SEG()
{
root=new Node();
}
void push(Node *node, ll tl, ll tr, ll k)
{
node->sum+=k;
node->cnt++;
if(tl==tr) return;
ll mid=(tl+tr-1)/2;
if(k<=mid)
{
if(node->lc==NULL) node->lc=new Node();
push(node->lc, tl, mid, k);
}
else
{
if(node->rc==NULL) node->rc=new Node();
push(node->rc, mid+1, tr, k);
}
}
void pop(Node *node, ll tl, ll tr, ll k)
{
node->sum-=k;
node->cnt--;
if(tl==tr) return;
ll mid=(tl+tr-1)/2;
if(k<=mid)
{
if(node->lc==NULL) assert(0);
pop(node->lc, tl, mid, k);
}
else
{
if(node->rc==NULL) assert(0);
pop(node->rc, mid+1, tr, k);
}
}
ll query(Node *node, ll tl, ll tr, ll k)
{
if(k<=0) return 0;
if(node->cnt==0) return 0;
if(tl==tr)
{
return tl*min(k, node->cnt);
}
ll mid=(tl+tr-1)/2;
if(node->lc==NULL) return query(node->rc, mid+1, tr, k);
if(node->rc==NULL) return query(node->lc, tl, mid, k);
if(node->lc->cnt>=k)
{
return query(node->lc, tl, mid, k);
}
else
{
return query(node->rc, mid+1, tr, k-node->lc->cnt)+node->lc->sum;
}
}
void push(ll k)
{
if(k>=0) return;
push(root, -1e15, 0, k);
}
void pop(ll k)
{
if(k>=0) return;
pop(root, -1e15, 0, k);
}
ll query(ll k)
{
return query(root, -1e15, 0, k);
}
};
SEG seg[MAXN+10];
ll sum[MAXN+10];
int chk[MAXN+10];
int chk2[MAXN+10];
bool vis[MAXN+10];
void dfs2(int now, int bef)
{
vis[now]=true;
while(!adj2[now].empty() && min(deg[E[adj2[now].back().second].u], deg[E[adj2[now].back().second].v])<=K)
{
//printf("??POP %d %d\n", now, adj2[now].back().first);
adj2[now].pop_back();
}
if(chk[par[now]]==0)
{
sum[par[now]]-=dp2[now];
seg[par[now]].pop(dp1[now]-dp2[now]);
}
for(auto nxt : adj2[now])
{
if(vis[nxt.first]) continue;
if(nxt.first==bef) continue;
dfs2(nxt.first, now);
}
dp1[now]=sum[now]+seg[now].query(K-1);
dp2[now]=sum[now]+seg[now].query(K)+E[val[now]].w;
//printf("%d : %lld %lld\n", now, dp1[now], dp2[now]);
if(chk[par[now]]==0)
{
sum[par[now]]+=dp2[now];
seg[par[now]].push(dp1[now]-dp2[now]);
}
}
vector<ll> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W)
{
N=_N;
for(int i=1; i<N; i++)
{
int u=_U[i-1]+1, v=_V[i-1]+1, w=_W[i-1];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
adj2[u].push_back({v, i});
adj2[v].push_back({u, i});
E[i]={u, v, w, i};
deg[u]++;
deg[v]++;
}
for(int i=1; i<=N; i++)
{
sort(adj2[i].begin(), adj2[i].end(), [&](const pii &p, const pii &q)
{
return min(deg[E[p.second].u], deg[E[p.second].v])>min(deg[E[q.second].u], deg[E[q.second].v]);
});
}
dfs(1, 1);
ans[0]=dp1[1];
for(int i=1; i<=N; i++)
{
sum[par[i]]+=dp2[i];
//printf("HIHI\n");
seg[par[i]].push(dp1[i]-dp2[i]);
}
vector<pii> V;
for(int i=1; i<=N; i++) V.push_back({deg[i], i});
sort(V.begin(), V.end());
for(int i=1, j=0; i<N; i++)
{
K=i;
//printf("K %d\n", K);
for(; j<V.size() && V[j].first<=K; j++)
{
int u=V[j].second;
chk[u]++;
if(chk[par[u]]==0)
{
sum[par[u]]-=dp2[u];
seg[par[u]].pop(dp1[u]-dp2[u]);
sum[par[u]]+=E[val[u]].w;
seg[par[u]].push(-E[val[u]].w);
}
for(auto it : adj[u])
{
chk2[it.second]++;
}
}
vector<int> VV;
for(int k=j; k<V.size(); k++)
{
VV.push_back(V[k].second);
}
sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
{
return dfn[p]<dfn[q];
});
for(int u : VV)
{
if(vis[u]) continue;
//printf("HI %d\n", u);
dfs2(u, u);
ans[K]+=min(dp1[u], dp2[u]);
}
for(int k=j; k<V.size(); k++)
{
int u=V[k].second;
vis[u]=false;
}
}
return vector<ll>(ans, ans+N);
}
Compilation message
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:216:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | for(; j<V.size() && V[j].first<=K; j++)
| ~^~~~~~~~~
roads.cpp:234:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
234 | for(int k=j; k<V.size(); k++)
| ~^~~~~~~~~
roads.cpp:249:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | for(int k=j; k<V.size(); k++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
13 ms |
12624 KB |
Output is correct |
3 |
Correct |
14 ms |
12796 KB |
Output is correct |
4 |
Correct |
11 ms |
10956 KB |
Output is correct |
5 |
Correct |
8 ms |
10628 KB |
Output is correct |
6 |
Correct |
8 ms |
10748 KB |
Output is correct |
7 |
Correct |
10 ms |
10492 KB |
Output is correct |
8 |
Correct |
10 ms |
10784 KB |
Output is correct |
9 |
Correct |
11 ms |
10832 KB |
Output is correct |
10 |
Correct |
8 ms |
10572 KB |
Output is correct |
11 |
Correct |
8 ms |
10572 KB |
Output is correct |
12 |
Correct |
120 ms |
21680 KB |
Output is correct |
13 |
Correct |
195 ms |
29168 KB |
Output is correct |
14 |
Correct |
335 ms |
84564 KB |
Output is correct |
15 |
Correct |
395 ms |
96616 KB |
Output is correct |
16 |
Correct |
387 ms |
95100 KB |
Output is correct |
17 |
Correct |
200 ms |
29992 KB |
Output is correct |
18 |
Correct |
10 ms |
10440 KB |
Output is correct |
19 |
Correct |
169 ms |
27400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10492 KB |
Output is correct |
2 |
Correct |
468 ms |
311432 KB |
Output is correct |
3 |
Correct |
482 ms |
312148 KB |
Output is correct |
4 |
Correct |
548 ms |
359500 KB |
Output is correct |
5 |
Correct |
430 ms |
277296 KB |
Output is correct |
6 |
Correct |
17 ms |
16708 KB |
Output is correct |
7 |
Correct |
20 ms |
17204 KB |
Output is correct |
8 |
Correct |
15 ms |
15312 KB |
Output is correct |
9 |
Correct |
9 ms |
11084 KB |
Output is correct |
10 |
Correct |
10 ms |
11084 KB |
Output is correct |
11 |
Correct |
9 ms |
10964 KB |
Output is correct |
12 |
Correct |
268 ms |
174960 KB |
Output is correct |
13 |
Correct |
437 ms |
281336 KB |
Output is correct |
14 |
Correct |
8 ms |
10496 KB |
Output is correct |
15 |
Correct |
375 ms |
250024 KB |
Output is correct |
16 |
Correct |
402 ms |
276216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
9 ms |
10480 KB |
Output is correct |
3 |
Correct |
8 ms |
10532 KB |
Output is correct |
4 |
Correct |
8 ms |
10956 KB |
Output is correct |
5 |
Correct |
9 ms |
10960 KB |
Output is correct |
6 |
Correct |
9 ms |
10572 KB |
Output is correct |
7 |
Correct |
11 ms |
10956 KB |
Output is correct |
8 |
Correct |
9 ms |
10700 KB |
Output is correct |
9 |
Correct |
9 ms |
10956 KB |
Output is correct |
10 |
Correct |
9 ms |
11084 KB |
Output is correct |
11 |
Correct |
9 ms |
11084 KB |
Output is correct |
12 |
Correct |
9 ms |
10964 KB |
Output is correct |
13 |
Correct |
10 ms |
10700 KB |
Output is correct |
14 |
Correct |
9 ms |
10796 KB |
Output is correct |
15 |
Correct |
8 ms |
10572 KB |
Output is correct |
16 |
Correct |
9 ms |
10700 KB |
Output is correct |
17 |
Correct |
9 ms |
10828 KB |
Output is correct |
18 |
Correct |
10 ms |
10700 KB |
Output is correct |
19 |
Correct |
9 ms |
10572 KB |
Output is correct |
20 |
Correct |
8 ms |
10572 KB |
Output is correct |
21 |
Correct |
8 ms |
10444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
9 ms |
10480 KB |
Output is correct |
3 |
Correct |
8 ms |
10532 KB |
Output is correct |
4 |
Correct |
8 ms |
10956 KB |
Output is correct |
5 |
Correct |
9 ms |
10960 KB |
Output is correct |
6 |
Correct |
9 ms |
10572 KB |
Output is correct |
7 |
Correct |
11 ms |
10956 KB |
Output is correct |
8 |
Correct |
9 ms |
10700 KB |
Output is correct |
9 |
Correct |
9 ms |
10956 KB |
Output is correct |
10 |
Correct |
9 ms |
11084 KB |
Output is correct |
11 |
Correct |
9 ms |
11084 KB |
Output is correct |
12 |
Correct |
9 ms |
10964 KB |
Output is correct |
13 |
Correct |
10 ms |
10700 KB |
Output is correct |
14 |
Correct |
9 ms |
10796 KB |
Output is correct |
15 |
Correct |
8 ms |
10572 KB |
Output is correct |
16 |
Correct |
9 ms |
10700 KB |
Output is correct |
17 |
Correct |
9 ms |
10828 KB |
Output is correct |
18 |
Correct |
10 ms |
10700 KB |
Output is correct |
19 |
Correct |
9 ms |
10572 KB |
Output is correct |
20 |
Correct |
8 ms |
10572 KB |
Output is correct |
21 |
Correct |
8 ms |
10444 KB |
Output is correct |
22 |
Correct |
8 ms |
10444 KB |
Output is correct |
23 |
Correct |
14 ms |
13724 KB |
Output is correct |
24 |
Correct |
20 ms |
15772 KB |
Output is correct |
25 |
Correct |
15 ms |
13444 KB |
Output is correct |
26 |
Correct |
16 ms |
12620 KB |
Output is correct |
27 |
Correct |
17 ms |
13684 KB |
Output is correct |
28 |
Correct |
12 ms |
10960 KB |
Output is correct |
29 |
Correct |
18 ms |
15152 KB |
Output is correct |
30 |
Correct |
16 ms |
13900 KB |
Output is correct |
31 |
Correct |
12 ms |
11148 KB |
Output is correct |
32 |
Correct |
11 ms |
10956 KB |
Output is correct |
33 |
Correct |
17 ms |
16716 KB |
Output is correct |
34 |
Correct |
18 ms |
17296 KB |
Output is correct |
35 |
Correct |
15 ms |
15188 KB |
Output is correct |
36 |
Correct |
14 ms |
12492 KB |
Output is correct |
37 |
Correct |
17 ms |
12776 KB |
Output is correct |
38 |
Correct |
11 ms |
10828 KB |
Output is correct |
39 |
Correct |
8 ms |
10468 KB |
Output is correct |
40 |
Correct |
8 ms |
10444 KB |
Output is correct |
41 |
Correct |
9 ms |
10956 KB |
Output is correct |
42 |
Correct |
12 ms |
11048 KB |
Output is correct |
43 |
Correct |
11 ms |
10552 KB |
Output is correct |
44 |
Correct |
9 ms |
11084 KB |
Output is correct |
45 |
Correct |
8 ms |
10700 KB |
Output is correct |
46 |
Correct |
9 ms |
10956 KB |
Output is correct |
47 |
Correct |
9 ms |
11084 KB |
Output is correct |
48 |
Correct |
9 ms |
11084 KB |
Output is correct |
49 |
Correct |
10 ms |
10956 KB |
Output is correct |
50 |
Correct |
8 ms |
10700 KB |
Output is correct |
51 |
Correct |
10 ms |
10700 KB |
Output is correct |
52 |
Correct |
8 ms |
10564 KB |
Output is correct |
53 |
Correct |
13 ms |
13112 KB |
Output is correct |
54 |
Correct |
17 ms |
13900 KB |
Output is correct |
55 |
Correct |
11 ms |
10956 KB |
Output is correct |
56 |
Correct |
11 ms |
10828 KB |
Output is correct |
57 |
Correct |
13 ms |
10828 KB |
Output is correct |
58 |
Correct |
8 ms |
10700 KB |
Output is correct |
59 |
Correct |
8 ms |
10828 KB |
Output is correct |
60 |
Correct |
9 ms |
10700 KB |
Output is correct |
61 |
Correct |
8 ms |
10572 KB |
Output is correct |
62 |
Correct |
11 ms |
10492 KB |
Output is correct |
63 |
Correct |
10 ms |
10544 KB |
Output is correct |
64 |
Correct |
14 ms |
13772 KB |
Output is correct |
65 |
Correct |
14 ms |
13772 KB |
Output is correct |
66 |
Correct |
11 ms |
10972 KB |
Output is correct |
67 |
Correct |
13 ms |
10916 KB |
Output is correct |
68 |
Correct |
12 ms |
11044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
564 ms |
171328 KB |
Output is correct |
2 |
Correct |
540 ms |
169932 KB |
Output is correct |
3 |
Correct |
257 ms |
31804 KB |
Output is correct |
4 |
Correct |
574 ms |
179124 KB |
Output is correct |
5 |
Correct |
255 ms |
31928 KB |
Output is correct |
6 |
Correct |
211 ms |
29304 KB |
Output is correct |
7 |
Correct |
444 ms |
118588 KB |
Output is correct |
8 |
Correct |
187 ms |
28216 KB |
Output is correct |
9 |
Correct |
511 ms |
140696 KB |
Output is correct |
10 |
Correct |
565 ms |
144016 KB |
Output is correct |
11 |
Correct |
255 ms |
31992 KB |
Output is correct |
12 |
Correct |
210 ms |
29468 KB |
Output is correct |
13 |
Correct |
8 ms |
10492 KB |
Output is correct |
14 |
Correct |
372 ms |
249796 KB |
Output is correct |
15 |
Correct |
406 ms |
276196 KB |
Output is correct |
16 |
Correct |
15 ms |
13772 KB |
Output is correct |
17 |
Correct |
14 ms |
13756 KB |
Output is correct |
18 |
Correct |
11 ms |
11004 KB |
Output is correct |
19 |
Correct |
11 ms |
10888 KB |
Output is correct |
20 |
Correct |
11 ms |
10956 KB |
Output is correct |
21 |
Correct |
182 ms |
27484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
564 ms |
171328 KB |
Output is correct |
2 |
Correct |
540 ms |
169932 KB |
Output is correct |
3 |
Correct |
257 ms |
31804 KB |
Output is correct |
4 |
Correct |
574 ms |
179124 KB |
Output is correct |
5 |
Correct |
255 ms |
31928 KB |
Output is correct |
6 |
Correct |
211 ms |
29304 KB |
Output is correct |
7 |
Correct |
444 ms |
118588 KB |
Output is correct |
8 |
Correct |
187 ms |
28216 KB |
Output is correct |
9 |
Correct |
511 ms |
140696 KB |
Output is correct |
10 |
Correct |
565 ms |
144016 KB |
Output is correct |
11 |
Correct |
255 ms |
31992 KB |
Output is correct |
12 |
Correct |
210 ms |
29468 KB |
Output is correct |
13 |
Correct |
8 ms |
10492 KB |
Output is correct |
14 |
Correct |
372 ms |
249796 KB |
Output is correct |
15 |
Correct |
406 ms |
276196 KB |
Output is correct |
16 |
Correct |
15 ms |
13772 KB |
Output is correct |
17 |
Correct |
14 ms |
13756 KB |
Output is correct |
18 |
Correct |
11 ms |
11004 KB |
Output is correct |
19 |
Correct |
11 ms |
10888 KB |
Output is correct |
20 |
Correct |
11 ms |
10956 KB |
Output is correct |
21 |
Correct |
182 ms |
27484 KB |
Output is correct |
22 |
Correct |
10 ms |
10492 KB |
Output is correct |
23 |
Correct |
8 ms |
10552 KB |
Output is correct |
24 |
Correct |
10 ms |
10492 KB |
Output is correct |
25 |
Correct |
526 ms |
161240 KB |
Output is correct |
26 |
Correct |
470 ms |
146012 KB |
Output is correct |
27 |
Correct |
622 ms |
185664 KB |
Output is correct |
28 |
Correct |
300 ms |
32064 KB |
Output is correct |
29 |
Correct |
240 ms |
30392 KB |
Output is correct |
30 |
Correct |
223 ms |
28744 KB |
Output is correct |
31 |
Correct |
228 ms |
29044 KB |
Output is correct |
32 |
Correct |
532 ms |
139064 KB |
Output is correct |
33 |
Correct |
184 ms |
28548 KB |
Output is correct |
34 |
Correct |
466 ms |
121068 KB |
Output is correct |
35 |
Correct |
631 ms |
163280 KB |
Output is correct |
36 |
Correct |
264 ms |
32368 KB |
Output is correct |
37 |
Correct |
216 ms |
29556 KB |
Output is correct |
38 |
Correct |
276 ms |
174896 KB |
Output is correct |
39 |
Correct |
439 ms |
281348 KB |
Output is correct |
40 |
Correct |
13 ms |
13132 KB |
Output is correct |
41 |
Correct |
16 ms |
14040 KB |
Output is correct |
42 |
Correct |
11 ms |
10956 KB |
Output is correct |
43 |
Correct |
10 ms |
10788 KB |
Output is correct |
44 |
Correct |
11 ms |
10856 KB |
Output is correct |
45 |
Correct |
8 ms |
10700 KB |
Output is correct |
46 |
Correct |
8 ms |
10812 KB |
Output is correct |
47 |
Correct |
8 ms |
10700 KB |
Output is correct |
48 |
Correct |
8 ms |
10572 KB |
Output is correct |
49 |
Correct |
10 ms |
10572 KB |
Output is correct |
50 |
Correct |
113 ms |
21800 KB |
Output is correct |
51 |
Correct |
194 ms |
29172 KB |
Output is correct |
52 |
Correct |
550 ms |
172740 KB |
Output is correct |
53 |
Correct |
529 ms |
170044 KB |
Output is correct |
54 |
Correct |
251 ms |
31804 KB |
Output is correct |
55 |
Correct |
564 ms |
179324 KB |
Output is correct |
56 |
Correct |
244 ms |
31800 KB |
Output is correct |
57 |
Correct |
231 ms |
29308 KB |
Output is correct |
58 |
Correct |
433 ms |
118648 KB |
Output is correct |
59 |
Correct |
180 ms |
28200 KB |
Output is correct |
60 |
Correct |
520 ms |
140708 KB |
Output is correct |
61 |
Correct |
535 ms |
144060 KB |
Output is correct |
62 |
Correct |
247 ms |
31932 KB |
Output is correct |
63 |
Correct |
206 ms |
29428 KB |
Output is correct |
64 |
Correct |
10 ms |
10444 KB |
Output is correct |
65 |
Correct |
370 ms |
249816 KB |
Output is correct |
66 |
Correct |
412 ms |
276332 KB |
Output is correct |
67 |
Correct |
14 ms |
13772 KB |
Output is correct |
68 |
Correct |
14 ms |
13836 KB |
Output is correct |
69 |
Correct |
11 ms |
11012 KB |
Output is correct |
70 |
Correct |
11 ms |
10956 KB |
Output is correct |
71 |
Correct |
11 ms |
11148 KB |
Output is correct |
72 |
Correct |
178 ms |
27404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
13 ms |
12624 KB |
Output is correct |
3 |
Correct |
14 ms |
12796 KB |
Output is correct |
4 |
Correct |
11 ms |
10956 KB |
Output is correct |
5 |
Correct |
8 ms |
10628 KB |
Output is correct |
6 |
Correct |
8 ms |
10748 KB |
Output is correct |
7 |
Correct |
10 ms |
10492 KB |
Output is correct |
8 |
Correct |
10 ms |
10784 KB |
Output is correct |
9 |
Correct |
11 ms |
10832 KB |
Output is correct |
10 |
Correct |
8 ms |
10572 KB |
Output is correct |
11 |
Correct |
8 ms |
10572 KB |
Output is correct |
12 |
Correct |
120 ms |
21680 KB |
Output is correct |
13 |
Correct |
195 ms |
29168 KB |
Output is correct |
14 |
Correct |
335 ms |
84564 KB |
Output is correct |
15 |
Correct |
395 ms |
96616 KB |
Output is correct |
16 |
Correct |
387 ms |
95100 KB |
Output is correct |
17 |
Correct |
200 ms |
29992 KB |
Output is correct |
18 |
Correct |
10 ms |
10440 KB |
Output is correct |
19 |
Correct |
169 ms |
27400 KB |
Output is correct |
20 |
Correct |
8 ms |
10492 KB |
Output is correct |
21 |
Correct |
468 ms |
311432 KB |
Output is correct |
22 |
Correct |
482 ms |
312148 KB |
Output is correct |
23 |
Correct |
548 ms |
359500 KB |
Output is correct |
24 |
Correct |
430 ms |
277296 KB |
Output is correct |
25 |
Correct |
17 ms |
16708 KB |
Output is correct |
26 |
Correct |
20 ms |
17204 KB |
Output is correct |
27 |
Correct |
15 ms |
15312 KB |
Output is correct |
28 |
Correct |
9 ms |
11084 KB |
Output is correct |
29 |
Correct |
10 ms |
11084 KB |
Output is correct |
30 |
Correct |
9 ms |
10964 KB |
Output is correct |
31 |
Correct |
268 ms |
174960 KB |
Output is correct |
32 |
Correct |
437 ms |
281336 KB |
Output is correct |
33 |
Correct |
8 ms |
10496 KB |
Output is correct |
34 |
Correct |
375 ms |
250024 KB |
Output is correct |
35 |
Correct |
402 ms |
276216 KB |
Output is correct |
36 |
Correct |
8 ms |
10444 KB |
Output is correct |
37 |
Correct |
9 ms |
10480 KB |
Output is correct |
38 |
Correct |
8 ms |
10532 KB |
Output is correct |
39 |
Correct |
8 ms |
10956 KB |
Output is correct |
40 |
Correct |
9 ms |
10960 KB |
Output is correct |
41 |
Correct |
9 ms |
10572 KB |
Output is correct |
42 |
Correct |
11 ms |
10956 KB |
Output is correct |
43 |
Correct |
9 ms |
10700 KB |
Output is correct |
44 |
Correct |
9 ms |
10956 KB |
Output is correct |
45 |
Correct |
9 ms |
11084 KB |
Output is correct |
46 |
Correct |
9 ms |
11084 KB |
Output is correct |
47 |
Correct |
9 ms |
10964 KB |
Output is correct |
48 |
Correct |
10 ms |
10700 KB |
Output is correct |
49 |
Correct |
9 ms |
10796 KB |
Output is correct |
50 |
Correct |
8 ms |
10572 KB |
Output is correct |
51 |
Correct |
9 ms |
10700 KB |
Output is correct |
52 |
Correct |
9 ms |
10828 KB |
Output is correct |
53 |
Correct |
10 ms |
10700 KB |
Output is correct |
54 |
Correct |
9 ms |
10572 KB |
Output is correct |
55 |
Correct |
8 ms |
10572 KB |
Output is correct |
56 |
Correct |
8 ms |
10444 KB |
Output is correct |
57 |
Correct |
8 ms |
10444 KB |
Output is correct |
58 |
Correct |
14 ms |
13724 KB |
Output is correct |
59 |
Correct |
20 ms |
15772 KB |
Output is correct |
60 |
Correct |
15 ms |
13444 KB |
Output is correct |
61 |
Correct |
16 ms |
12620 KB |
Output is correct |
62 |
Correct |
17 ms |
13684 KB |
Output is correct |
63 |
Correct |
12 ms |
10960 KB |
Output is correct |
64 |
Correct |
18 ms |
15152 KB |
Output is correct |
65 |
Correct |
16 ms |
13900 KB |
Output is correct |
66 |
Correct |
12 ms |
11148 KB |
Output is correct |
67 |
Correct |
11 ms |
10956 KB |
Output is correct |
68 |
Correct |
17 ms |
16716 KB |
Output is correct |
69 |
Correct |
18 ms |
17296 KB |
Output is correct |
70 |
Correct |
15 ms |
15188 KB |
Output is correct |
71 |
Correct |
14 ms |
12492 KB |
Output is correct |
72 |
Correct |
17 ms |
12776 KB |
Output is correct |
73 |
Correct |
11 ms |
10828 KB |
Output is correct |
74 |
Correct |
8 ms |
10468 KB |
Output is correct |
75 |
Correct |
8 ms |
10444 KB |
Output is correct |
76 |
Correct |
9 ms |
10956 KB |
Output is correct |
77 |
Correct |
12 ms |
11048 KB |
Output is correct |
78 |
Correct |
11 ms |
10552 KB |
Output is correct |
79 |
Correct |
9 ms |
11084 KB |
Output is correct |
80 |
Correct |
8 ms |
10700 KB |
Output is correct |
81 |
Correct |
9 ms |
10956 KB |
Output is correct |
82 |
Correct |
9 ms |
11084 KB |
Output is correct |
83 |
Correct |
9 ms |
11084 KB |
Output is correct |
84 |
Correct |
10 ms |
10956 KB |
Output is correct |
85 |
Correct |
8 ms |
10700 KB |
Output is correct |
86 |
Correct |
10 ms |
10700 KB |
Output is correct |
87 |
Correct |
8 ms |
10564 KB |
Output is correct |
88 |
Correct |
13 ms |
13112 KB |
Output is correct |
89 |
Correct |
17 ms |
13900 KB |
Output is correct |
90 |
Correct |
11 ms |
10956 KB |
Output is correct |
91 |
Correct |
11 ms |
10828 KB |
Output is correct |
92 |
Correct |
13 ms |
10828 KB |
Output is correct |
93 |
Correct |
8 ms |
10700 KB |
Output is correct |
94 |
Correct |
8 ms |
10828 KB |
Output is correct |
95 |
Correct |
9 ms |
10700 KB |
Output is correct |
96 |
Correct |
8 ms |
10572 KB |
Output is correct |
97 |
Correct |
11 ms |
10492 KB |
Output is correct |
98 |
Correct |
10 ms |
10544 KB |
Output is correct |
99 |
Correct |
14 ms |
13772 KB |
Output is correct |
100 |
Correct |
14 ms |
13772 KB |
Output is correct |
101 |
Correct |
11 ms |
10972 KB |
Output is correct |
102 |
Correct |
13 ms |
10916 KB |
Output is correct |
103 |
Correct |
12 ms |
11044 KB |
Output is correct |
104 |
Correct |
564 ms |
171328 KB |
Output is correct |
105 |
Correct |
540 ms |
169932 KB |
Output is correct |
106 |
Correct |
257 ms |
31804 KB |
Output is correct |
107 |
Correct |
574 ms |
179124 KB |
Output is correct |
108 |
Correct |
255 ms |
31928 KB |
Output is correct |
109 |
Correct |
211 ms |
29304 KB |
Output is correct |
110 |
Correct |
444 ms |
118588 KB |
Output is correct |
111 |
Correct |
187 ms |
28216 KB |
Output is correct |
112 |
Correct |
511 ms |
140696 KB |
Output is correct |
113 |
Correct |
565 ms |
144016 KB |
Output is correct |
114 |
Correct |
255 ms |
31992 KB |
Output is correct |
115 |
Correct |
210 ms |
29468 KB |
Output is correct |
116 |
Correct |
8 ms |
10492 KB |
Output is correct |
117 |
Correct |
372 ms |
249796 KB |
Output is correct |
118 |
Correct |
406 ms |
276196 KB |
Output is correct |
119 |
Correct |
15 ms |
13772 KB |
Output is correct |
120 |
Correct |
14 ms |
13756 KB |
Output is correct |
121 |
Correct |
11 ms |
11004 KB |
Output is correct |
122 |
Correct |
11 ms |
10888 KB |
Output is correct |
123 |
Correct |
11 ms |
10956 KB |
Output is correct |
124 |
Correct |
182 ms |
27484 KB |
Output is correct |
125 |
Correct |
10 ms |
10492 KB |
Output is correct |
126 |
Correct |
8 ms |
10552 KB |
Output is correct |
127 |
Correct |
10 ms |
10492 KB |
Output is correct |
128 |
Correct |
526 ms |
161240 KB |
Output is correct |
129 |
Correct |
470 ms |
146012 KB |
Output is correct |
130 |
Correct |
622 ms |
185664 KB |
Output is correct |
131 |
Correct |
300 ms |
32064 KB |
Output is correct |
132 |
Correct |
240 ms |
30392 KB |
Output is correct |
133 |
Correct |
223 ms |
28744 KB |
Output is correct |
134 |
Correct |
228 ms |
29044 KB |
Output is correct |
135 |
Correct |
532 ms |
139064 KB |
Output is correct |
136 |
Correct |
184 ms |
28548 KB |
Output is correct |
137 |
Correct |
466 ms |
121068 KB |
Output is correct |
138 |
Correct |
631 ms |
163280 KB |
Output is correct |
139 |
Correct |
264 ms |
32368 KB |
Output is correct |
140 |
Correct |
216 ms |
29556 KB |
Output is correct |
141 |
Correct |
276 ms |
174896 KB |
Output is correct |
142 |
Correct |
439 ms |
281348 KB |
Output is correct |
143 |
Correct |
13 ms |
13132 KB |
Output is correct |
144 |
Correct |
16 ms |
14040 KB |
Output is correct |
145 |
Correct |
11 ms |
10956 KB |
Output is correct |
146 |
Correct |
10 ms |
10788 KB |
Output is correct |
147 |
Correct |
11 ms |
10856 KB |
Output is correct |
148 |
Correct |
8 ms |
10700 KB |
Output is correct |
149 |
Correct |
8 ms |
10812 KB |
Output is correct |
150 |
Correct |
8 ms |
10700 KB |
Output is correct |
151 |
Correct |
8 ms |
10572 KB |
Output is correct |
152 |
Correct |
10 ms |
10572 KB |
Output is correct |
153 |
Correct |
113 ms |
21800 KB |
Output is correct |
154 |
Correct |
194 ms |
29172 KB |
Output is correct |
155 |
Correct |
550 ms |
172740 KB |
Output is correct |
156 |
Correct |
529 ms |
170044 KB |
Output is correct |
157 |
Correct |
251 ms |
31804 KB |
Output is correct |
158 |
Correct |
564 ms |
179324 KB |
Output is correct |
159 |
Correct |
244 ms |
31800 KB |
Output is correct |
160 |
Correct |
231 ms |
29308 KB |
Output is correct |
161 |
Correct |
433 ms |
118648 KB |
Output is correct |
162 |
Correct |
180 ms |
28200 KB |
Output is correct |
163 |
Correct |
520 ms |
140708 KB |
Output is correct |
164 |
Correct |
535 ms |
144060 KB |
Output is correct |
165 |
Correct |
247 ms |
31932 KB |
Output is correct |
166 |
Correct |
206 ms |
29428 KB |
Output is correct |
167 |
Correct |
10 ms |
10444 KB |
Output is correct |
168 |
Correct |
370 ms |
249816 KB |
Output is correct |
169 |
Correct |
412 ms |
276332 KB |
Output is correct |
170 |
Correct |
14 ms |
13772 KB |
Output is correct |
171 |
Correct |
14 ms |
13836 KB |
Output is correct |
172 |
Correct |
11 ms |
11012 KB |
Output is correct |
173 |
Correct |
11 ms |
10956 KB |
Output is correct |
174 |
Correct |
11 ms |
11148 KB |
Output is correct |
175 |
Correct |
178 ms |
27404 KB |
Output is correct |
176 |
Correct |
10 ms |
10444 KB |
Output is correct |
177 |
Correct |
802 ms |
282796 KB |
Output is correct |
178 |
Correct |
595 ms |
214844 KB |
Output is correct |
179 |
Correct |
296 ms |
31928 KB |
Output is correct |
180 |
Correct |
645 ms |
165568 KB |
Output is correct |
181 |
Correct |
265 ms |
32788 KB |
Output is correct |
182 |
Correct |
274 ms |
31988 KB |
Output is correct |
183 |
Correct |
499 ms |
119908 KB |
Output is correct |
184 |
Correct |
550 ms |
144960 KB |
Output is correct |
185 |
Correct |
496 ms |
135920 KB |
Output is correct |
186 |
Correct |
491 ms |
130280 KB |
Output is correct |
187 |
Correct |
402 ms |
92716 KB |
Output is correct |
188 |
Correct |
587 ms |
174408 KB |
Output is correct |
189 |
Correct |
599 ms |
160840 KB |
Output is correct |
190 |
Correct |
605 ms |
146724 KB |
Output is correct |
191 |
Correct |
303 ms |
32068 KB |
Output is correct |
192 |
Correct |
439 ms |
97252 KB |
Output is correct |
193 |
Correct |
545 ms |
131240 KB |
Output is correct |
194 |
Correct |
273 ms |
32832 KB |
Output is correct |
195 |
Correct |
457 ms |
312504 KB |
Output is correct |
196 |
Correct |
493 ms |
312232 KB |
Output is correct |
197 |
Correct |
554 ms |
359612 KB |
Output is correct |
198 |
Correct |
432 ms |
277124 KB |
Output is correct |
199 |
Correct |
14 ms |
13772 KB |
Output is correct |
200 |
Correct |
21 ms |
15812 KB |
Output is correct |
201 |
Correct |
14 ms |
13452 KB |
Output is correct |
202 |
Correct |
14 ms |
12620 KB |
Output is correct |
203 |
Correct |
16 ms |
13712 KB |
Output is correct |
204 |
Correct |
12 ms |
10980 KB |
Output is correct |
205 |
Correct |
18 ms |
15180 KB |
Output is correct |
206 |
Correct |
16 ms |
13900 KB |
Output is correct |
207 |
Correct |
12 ms |
11212 KB |
Output is correct |
208 |
Correct |
11 ms |
10956 KB |
Output is correct |
209 |
Correct |
19 ms |
16776 KB |
Output is correct |
210 |
Correct |
19 ms |
17128 KB |
Output is correct |
211 |
Correct |
15 ms |
15240 KB |
Output is correct |
212 |
Correct |
14 ms |
12584 KB |
Output is correct |
213 |
Correct |
14 ms |
12748 KB |
Output is correct |
214 |
Correct |
11 ms |
10956 KB |
Output is correct |
215 |
Correct |
8 ms |
10492 KB |
Output is correct |
216 |
Correct |
11 ms |
10444 KB |
Output is correct |
217 |
Correct |
9 ms |
10956 KB |
Output is correct |
218 |
Correct |
9 ms |
10956 KB |
Output is correct |
219 |
Correct |
9 ms |
10560 KB |
Output is correct |
220 |
Correct |
9 ms |
10956 KB |
Output is correct |
221 |
Correct |
8 ms |
10748 KB |
Output is correct |
222 |
Correct |
9 ms |
10956 KB |
Output is correct |
223 |
Correct |
10 ms |
11068 KB |
Output is correct |
224 |
Correct |
9 ms |
11120 KB |
Output is correct |
225 |
Correct |
9 ms |
10956 KB |
Output is correct |
226 |
Correct |
9 ms |
10664 KB |
Output is correct |
227 |
Correct |
11 ms |
10700 KB |
Output is correct |
228 |
Correct |
9 ms |
10584 KB |
Output is correct |
229 |
Correct |
518 ms |
161372 KB |
Output is correct |
230 |
Correct |
466 ms |
145976 KB |
Output is correct |
231 |
Correct |
619 ms |
185672 KB |
Output is correct |
232 |
Correct |
276 ms |
32004 KB |
Output is correct |
233 |
Correct |
261 ms |
30532 KB |
Output is correct |
234 |
Correct |
237 ms |
28728 KB |
Output is correct |
235 |
Correct |
233 ms |
29052 KB |
Output is correct |
236 |
Correct |
542 ms |
139064 KB |
Output is correct |
237 |
Correct |
191 ms |
28584 KB |
Output is correct |
238 |
Correct |
471 ms |
121080 KB |
Output is correct |
239 |
Correct |
640 ms |
163260 KB |
Output is correct |
240 |
Correct |
280 ms |
32312 KB |
Output is correct |
241 |
Correct |
222 ms |
29652 KB |
Output is correct |
242 |
Correct |
278 ms |
174908 KB |
Output is correct |
243 |
Correct |
435 ms |
281476 KB |
Output is correct |
244 |
Correct |
14 ms |
13132 KB |
Output is correct |
245 |
Correct |
15 ms |
14052 KB |
Output is correct |
246 |
Correct |
12 ms |
10956 KB |
Output is correct |
247 |
Correct |
11 ms |
10760 KB |
Output is correct |
248 |
Correct |
11 ms |
10828 KB |
Output is correct |
249 |
Correct |
9 ms |
10708 KB |
Output is correct |
250 |
Correct |
9 ms |
10828 KB |
Output is correct |
251 |
Correct |
9 ms |
10700 KB |
Output is correct |
252 |
Correct |
8 ms |
10572 KB |
Output is correct |
253 |
Correct |
8 ms |
10504 KB |
Output is correct |
254 |
Correct |
117 ms |
21816 KB |
Output is correct |
255 |
Correct |
207 ms |
29140 KB |
Output is correct |
256 |
Correct |
360 ms |
84652 KB |
Output is correct |
257 |
Correct |
418 ms |
96644 KB |
Output is correct |
258 |
Correct |
399 ms |
95004 KB |
Output is correct |
259 |
Correct |
203 ms |
30124 KB |
Output is correct |
260 |
Correct |
579 ms |
172636 KB |
Output is correct |
261 |
Correct |
553 ms |
170040 KB |
Output is correct |
262 |
Correct |
264 ms |
31932 KB |
Output is correct |
263 |
Correct |
581 ms |
179144 KB |
Output is correct |
264 |
Correct |
260 ms |
31896 KB |
Output is correct |
265 |
Correct |
228 ms |
29316 KB |
Output is correct |
266 |
Correct |
440 ms |
118588 KB |
Output is correct |
267 |
Correct |
182 ms |
28188 KB |
Output is correct |
268 |
Correct |
526 ms |
140820 KB |
Output is correct |
269 |
Correct |
535 ms |
143996 KB |
Output is correct |
270 |
Correct |
260 ms |
31968 KB |
Output is correct |
271 |
Correct |
207 ms |
29496 KB |
Output is correct |
272 |
Correct |
10 ms |
10524 KB |
Output is correct |
273 |
Correct |
364 ms |
249952 KB |
Output is correct |
274 |
Correct |
396 ms |
276148 KB |
Output is correct |
275 |
Correct |
17 ms |
13836 KB |
Output is correct |
276 |
Correct |
16 ms |
13772 KB |
Output is correct |
277 |
Correct |
13 ms |
11136 KB |
Output is correct |
278 |
Correct |
12 ms |
10932 KB |
Output is correct |
279 |
Correct |
13 ms |
10960 KB |
Output is correct |
280 |
Correct |
176 ms |
27436 KB |
Output is correct |