#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const ll N = 1e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
ll n;
set<ii> Adj[N];
ll k;
ll dp[N][2];
bool vis[N];
map<ii, int> mp;
int cnt[N];
vector<ll> bit1[N], bit2[N];
void upd(int u, int pos, int val){
//cout << "UPD " << u << " " << pos << " " << val << "\n";
int pos1 = pos, pos2 = pos;
for(; pos1 < bit1[u].size(); pos1 += pos1 & -pos1) bit1[u][pos1]++;
for(; pos2 < bit2[u].size(); pos2 += pos2 & -pos2) bit2[u][pos2] += val;
}
ll get(int u, int pos){
int itr = 0;
ll ans = 0;
for(int i = 19; i >= 0; i--){
if(itr + (1LL << i) >= bit1[u].size()) continue;
if(pos >= bit1[u][itr + (1LL << i)]){
pos -= bit1[u][itr + (1LL << i)];
ans += bit2[u][itr + (1LL << i)];
itr += (1LL << i);
}
}
return ans;
}
void dfs(int u, int p, int we){
vis[u] = 1;
//int we = 0;
for(auto it : Adj[u]){
int v = it.fi;
if(v == p){
//we = it.se;
continue;
}
//assert(Adj[v].size() > k);
//if(Adj[v].size() <= k) continue;
dfs(v, u, it.se);
}
vector<ll> vc;
ll sum = 0;
for(auto it : Adj[u]){
int v = it.fi;
if(v == p) continue;
//cout << "EDG " << u << " " << v << "\n";
sum += dp[v][0];
if(dp[v][0] > dp[v][1]) vc.pb(dp[v][0] - dp[v][1]);
}
sort(vc.begin(), vc.end());
reverse(vc.begin(), vc.end());
sum += get(u, cnt[u]);
ll sum2 = 0, opt = -oo;
//cout << cnt[u] << "\n";
for(int i = 0; i <= vc.size(); i++){
if((k - 1) < i) break;
opt = max(opt, sum2 + get(u, k - 1 - i));
if(i == vc.size()) break;
sum2 += vc[i];
}
//cout << "OK " << cnt[u] << " " << get(u, cnt[u]) << " " << sum << " " << opt << "\n";
dp[u][1] = sum - opt;
sum2 = 0, opt = -oo;
//cout << vc.size() << "\n";
for(int i = 0; i <= vc.size(); i++){
if(k < i) break;
opt = max(opt, sum2 + get(u, k - i));
if(i == vc.size()) break;
sum2 += vc[i];
}
dp[u][0] = sum - opt + we;
//cout << u << " " << dp[u][0] << " " << dp[u][1] << "\n";
/*
for(int i = 0; i < min((ll)vc.size(), (ll)k - 1); i++){
sum2 += max(0LL, vc[i]);
}*/
/*
dp[u][0] = sum - sum2 - (((ll)vc.size() < k || !k) ? 0 : max(0LL, vc[k - 1])) + we;
dp[u][1] = sum - sum2;*/
//cout << u << " " << dp[u][0] << " " << dp[u][1] << "\n";
}
bool ck_star(){
int tol = 0;
for(int i = 1; i <= n; i++) tol += (Adj[i].size() >= 2);
return (tol == 1);
}
bool ck_line(){
for(int i = 1; i <= n; i++) if(Adj[i].size() > 2) return 0;
return 1;
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W){
n = N;
//cout << U.size() << " " << V.size() << " " << W.size() << "\n";
//exit(0);
for(int i = 0; i < (n - 1); i++){
U[i]++, V[i]++;
Adj[U[i]].insert({V[i], W[i]});
Adj[V[i]].insert({U[i], W[i]});
}
set<ii> nodes;
for(int i = 1; i <= n; i++) nodes.insert({Adj[i].size(), i});
for(int i = 1; i <= n; i++){
bit1[i].resize(Adj[i].size() + 1);
bit2[i].resize(Adj[i].size() + 1);
int cnt = 0;
vector<ii> temp;
for(auto it : Adj[i]) temp.pb({it.se, it.fi});
sort(temp.begin(), temp.end(), greater<ii>());
for(auto it : temp){
if(it.fi <= 0) break;
cnt++;
mp[{i, it.se}] = cnt;
}
}
/*
if(ck_star()){
sort(W.begin(), W.end(), greater<int>());
vector<ll> ans(n);
ll sum = 0;
for(int i = n - 1; i >= 0; i--){
ans[i] = sum;
if(i) sum += W[i - 1];
}
return ans;
}*/
int mx_deg = 0;
for(int i = 1; i <= n; i++) mx_deg = max(mx_deg, (int)Adj[i].size());
vector<ll> ans;
//cout << "OK\n";
for(int i = 0; i < mx_deg; i++){
k = i;
while(nodes.size() && (*nodes.begin()).fi <= k){
int u = (*nodes.begin()).se;
for(auto it : Adj[u]){
int v = it.fi, w = it.se;
cnt[v]++;
if(mp.find({v, u}) != mp.end()) upd(v, mp[{v, u}], w);
//Adj[u].erase({v, w});
Adj[v].erase({u, w});
}
Adj[u].clear();
//cout << u << " " << i << "\n";
nodes.erase(nodes.begin());
}
for(auto it : nodes) vis[it.se] = 0;
ll answ = 0;
//cout << i << "\n";
for(auto it : nodes){
//assert(Adj[it.se].size() > k);
if(!vis[it.se]){
//cout << i << " " << it.se << "\n";
dfs(it.se, it.se, 0);
answ += min(dp[it.se][0], dp[it.se][1]);
}
}
ans.pb(answ);
/*
k = i;
dfs(1, 1);
ans.pb(min(dp[1][0], dp[1][1]));*/
}
for(int i = mx_deg; i < n; i++) ans.pb(0);
return ans;
}
/*
void process(){
int n;
vector<int> a, b, c;
cin >> n;
for(int i = 1; i <= 3 * n - 3; i++){
int x;
cin >> x;
if(i <= (n - 1)) a.pb(x);
else if(i <= 2 * (n - 1)) b.pb(x);
else c.pb(x);
}
vector<long long> temp = minimum_closure_costs(n, a, b, c);
for(auto it : temp) cout << it << " ";
}
signed main(){
ios_base::sync_with_stdio(0);
freopen("roads.inp", "r", stdin);
freopen("roads.out", "w", stdout);
process();
}*/
Compilation message
roads.cpp: In function 'void upd(int, int, int)':
roads.cpp:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(; pos1 < bit1[u].size(); pos1 += pos1 & -pos1) bit1[u][pos1]++;
| ~~~~~^~~~~~~~~~~~~~~~
roads.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(; pos2 < bit2[u].size(); pos2 += pos2 & -pos2) bit2[u][pos2] += val;
| ~~~~~^~~~~~~~~~~~~~~~
roads.cpp: In function 'long long int get(int, int)':
roads.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if(itr + (1LL << i) >= bit1[u].size()) continue;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i = 0; i <= vc.size(); i++){
| ~~^~~~~~~~~~~~
roads.cpp:82:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(i == vc.size()) break;
| ~~^~~~~~~~~~~~
roads.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i <= vc.size(); i++){
| ~~^~~~~~~~~~~~
roads.cpp:92:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | if(i == vc.size()) break;
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9708 KB |
Output is correct |
2 |
Correct |
9 ms |
10488 KB |
Output is correct |
3 |
Correct |
10 ms |
10492 KB |
Output is correct |
4 |
Correct |
9 ms |
10540 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 |
8 ms |
10296 KB |
Output is correct |
9 |
Correct |
9 ms |
10452 KB |
Output is correct |
10 |
Correct |
6 ms |
9764 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
178 ms |
33308 KB |
Output is correct |
13 |
Correct |
310 ms |
49036 KB |
Output is correct |
14 |
Correct |
307 ms |
45592 KB |
Output is correct |
15 |
Correct |
310 ms |
49396 KB |
Output is correct |
16 |
Correct |
319 ms |
49936 KB |
Output is correct |
17 |
Correct |
309 ms |
49924 KB |
Output is correct |
18 |
Correct |
5 ms |
9708 KB |
Output is correct |
19 |
Correct |
249 ms |
45304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
144 ms |
57308 KB |
Output is correct |
3 |
Correct |
160 ms |
63016 KB |
Output is correct |
4 |
Correct |
175 ms |
66492 KB |
Output is correct |
5 |
Correct |
183 ms |
66408 KB |
Output is correct |
6 |
Correct |
8 ms |
10656 KB |
Output is correct |
7 |
Correct |
9 ms |
10856 KB |
Output is correct |
8 |
Correct |
7 ms |
10708 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9812 KB |
Output is correct |
11 |
Correct |
6 ms |
9812 KB |
Output is correct |
12 |
Correct |
107 ms |
43528 KB |
Output is correct |
13 |
Correct |
174 ms |
66292 KB |
Output is correct |
14 |
Correct |
5 ms |
9708 KB |
Output is correct |
15 |
Correct |
150 ms |
60788 KB |
Output is correct |
16 |
Correct |
167 ms |
66292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9624 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9708 KB |
Output is correct |
5 |
Correct |
6 ms |
9760 KB |
Output is correct |
6 |
Correct |
6 ms |
9784 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9756 KB |
Output is correct |
11 |
Correct |
6 ms |
9812 KB |
Output is correct |
12 |
Correct |
7 ms |
9812 KB |
Output is correct |
13 |
Correct |
6 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9712 KB |
Output is correct |
15 |
Correct |
6 ms |
9704 KB |
Output is correct |
16 |
Correct |
5 ms |
9704 KB |
Output is correct |
17 |
Correct |
5 ms |
9704 KB |
Output is correct |
18 |
Correct |
7 ms |
9692 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9720 KB |
Output is correct |
21 |
Correct |
5 ms |
9640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9624 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9708 KB |
Output is correct |
5 |
Correct |
6 ms |
9760 KB |
Output is correct |
6 |
Correct |
6 ms |
9784 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9756 KB |
Output is correct |
11 |
Correct |
6 ms |
9812 KB |
Output is correct |
12 |
Correct |
7 ms |
9812 KB |
Output is correct |
13 |
Correct |
6 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9712 KB |
Output is correct |
15 |
Correct |
6 ms |
9704 KB |
Output is correct |
16 |
Correct |
5 ms |
9704 KB |
Output is correct |
17 |
Correct |
5 ms |
9704 KB |
Output is correct |
18 |
Correct |
7 ms |
9692 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9720 KB |
Output is correct |
21 |
Correct |
5 ms |
9640 KB |
Output is correct |
22 |
Correct |
5 ms |
9684 KB |
Output is correct |
23 |
Correct |
7 ms |
10196 KB |
Output is correct |
24 |
Correct |
10 ms |
10612 KB |
Output is correct |
25 |
Correct |
9 ms |
10360 KB |
Output is correct |
26 |
Correct |
10 ms |
10452 KB |
Output is correct |
27 |
Correct |
11 ms |
10424 KB |
Output is correct |
28 |
Correct |
9 ms |
10452 KB |
Output is correct |
29 |
Correct |
9 ms |
10452 KB |
Output is correct |
30 |
Correct |
9 ms |
10452 KB |
Output is correct |
31 |
Correct |
9 ms |
10468 KB |
Output is correct |
32 |
Correct |
9 ms |
10452 KB |
Output is correct |
33 |
Correct |
9 ms |
10592 KB |
Output is correct |
34 |
Correct |
8 ms |
10836 KB |
Output is correct |
35 |
Correct |
8 ms |
10740 KB |
Output is correct |
36 |
Correct |
10 ms |
10452 KB |
Output is correct |
37 |
Correct |
11 ms |
10656 KB |
Output is correct |
38 |
Correct |
11 ms |
10452 KB |
Output is correct |
39 |
Correct |
5 ms |
9684 KB |
Output is correct |
40 |
Correct |
6 ms |
9684 KB |
Output is correct |
41 |
Correct |
5 ms |
9684 KB |
Output is correct |
42 |
Correct |
6 ms |
9716 KB |
Output is correct |
43 |
Correct |
6 ms |
9684 KB |
Output is correct |
44 |
Correct |
6 ms |
9684 KB |
Output is correct |
45 |
Correct |
5 ms |
9684 KB |
Output is correct |
46 |
Correct |
6 ms |
9684 KB |
Output is correct |
47 |
Correct |
6 ms |
9684 KB |
Output is correct |
48 |
Correct |
6 ms |
9812 KB |
Output is correct |
49 |
Correct |
6 ms |
9812 KB |
Output is correct |
50 |
Correct |
6 ms |
9660 KB |
Output is correct |
51 |
Correct |
6 ms |
9712 KB |
Output is correct |
52 |
Correct |
6 ms |
9684 KB |
Output is correct |
53 |
Correct |
8 ms |
10228 KB |
Output is correct |
54 |
Correct |
9 ms |
10452 KB |
Output is correct |
55 |
Correct |
9 ms |
10452 KB |
Output is correct |
56 |
Correct |
8 ms |
10324 KB |
Output is correct |
57 |
Correct |
9 ms |
10388 KB |
Output is correct |
58 |
Correct |
6 ms |
9708 KB |
Output is correct |
59 |
Correct |
6 ms |
9684 KB |
Output is correct |
60 |
Correct |
6 ms |
9704 KB |
Output is correct |
61 |
Correct |
5 ms |
9684 KB |
Output is correct |
62 |
Correct |
5 ms |
9684 KB |
Output is correct |
63 |
Correct |
5 ms |
9684 KB |
Output is correct |
64 |
Correct |
9 ms |
10452 KB |
Output is correct |
65 |
Correct |
9 ms |
10392 KB |
Output is correct |
66 |
Correct |
10 ms |
10452 KB |
Output is correct |
67 |
Correct |
9 ms |
10452 KB |
Output is correct |
68 |
Correct |
9 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
402 ms |
48184 KB |
Output is correct |
2 |
Correct |
426 ms |
47484 KB |
Output is correct |
3 |
Correct |
345 ms |
49944 KB |
Output is correct |
4 |
Correct |
422 ms |
49396 KB |
Output is correct |
5 |
Correct |
321 ms |
50852 KB |
Output is correct |
6 |
Correct |
316 ms |
50336 KB |
Output is correct |
7 |
Correct |
397 ms |
49400 KB |
Output is correct |
8 |
Correct |
266 ms |
46408 KB |
Output is correct |
9 |
Correct |
333 ms |
54932 KB |
Output is correct |
10 |
Correct |
398 ms |
48328 KB |
Output is correct |
11 |
Correct |
338 ms |
49872 KB |
Output is correct |
12 |
Correct |
296 ms |
49568 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
157 ms |
60796 KB |
Output is correct |
15 |
Correct |
182 ms |
66192 KB |
Output is correct |
16 |
Correct |
13 ms |
10452 KB |
Output is correct |
17 |
Correct |
10 ms |
10452 KB |
Output is correct |
18 |
Correct |
9 ms |
10452 KB |
Output is correct |
19 |
Correct |
9 ms |
10484 KB |
Output is correct |
20 |
Correct |
10 ms |
10520 KB |
Output is correct |
21 |
Correct |
253 ms |
45364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
402 ms |
48184 KB |
Output is correct |
2 |
Correct |
426 ms |
47484 KB |
Output is correct |
3 |
Correct |
345 ms |
49944 KB |
Output is correct |
4 |
Correct |
422 ms |
49396 KB |
Output is correct |
5 |
Correct |
321 ms |
50852 KB |
Output is correct |
6 |
Correct |
316 ms |
50336 KB |
Output is correct |
7 |
Correct |
397 ms |
49400 KB |
Output is correct |
8 |
Correct |
266 ms |
46408 KB |
Output is correct |
9 |
Correct |
333 ms |
54932 KB |
Output is correct |
10 |
Correct |
398 ms |
48328 KB |
Output is correct |
11 |
Correct |
338 ms |
49872 KB |
Output is correct |
12 |
Correct |
296 ms |
49568 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
157 ms |
60796 KB |
Output is correct |
15 |
Correct |
182 ms |
66192 KB |
Output is correct |
16 |
Correct |
13 ms |
10452 KB |
Output is correct |
17 |
Correct |
10 ms |
10452 KB |
Output is correct |
18 |
Correct |
9 ms |
10452 KB |
Output is correct |
19 |
Correct |
9 ms |
10484 KB |
Output is correct |
20 |
Correct |
10 ms |
10520 KB |
Output is correct |
21 |
Correct |
253 ms |
45364 KB |
Output is correct |
22 |
Correct |
6 ms |
9684 KB |
Output is correct |
23 |
Correct |
6 ms |
9656 KB |
Output is correct |
24 |
Correct |
5 ms |
9684 KB |
Output is correct |
25 |
Correct |
344 ms |
43628 KB |
Output is correct |
26 |
Correct |
305 ms |
40368 KB |
Output is correct |
27 |
Correct |
417 ms |
49480 KB |
Output is correct |
28 |
Correct |
357 ms |
49784 KB |
Output is correct |
29 |
Correct |
343 ms |
47668 KB |
Output is correct |
30 |
Correct |
316 ms |
48816 KB |
Output is correct |
31 |
Correct |
327 ms |
48968 KB |
Output is correct |
32 |
Correct |
426 ms |
46140 KB |
Output is correct |
33 |
Correct |
318 ms |
47328 KB |
Output is correct |
34 |
Correct |
413 ms |
49456 KB |
Output is correct |
35 |
Correct |
379 ms |
59088 KB |
Output is correct |
36 |
Correct |
348 ms |
49848 KB |
Output is correct |
37 |
Correct |
307 ms |
49580 KB |
Output is correct |
38 |
Correct |
96 ms |
43472 KB |
Output is correct |
39 |
Correct |
172 ms |
66252 KB |
Output is correct |
40 |
Correct |
10 ms |
10324 KB |
Output is correct |
41 |
Correct |
10 ms |
10484 KB |
Output is correct |
42 |
Correct |
9 ms |
10504 KB |
Output is correct |
43 |
Correct |
8 ms |
10264 KB |
Output is correct |
44 |
Correct |
8 ms |
10452 KB |
Output is correct |
45 |
Correct |
6 ms |
9812 KB |
Output is correct |
46 |
Correct |
5 ms |
9704 KB |
Output is correct |
47 |
Correct |
6 ms |
9736 KB |
Output is correct |
48 |
Correct |
7 ms |
9684 KB |
Output is correct |
49 |
Correct |
5 ms |
9720 KB |
Output is correct |
50 |
Correct |
178 ms |
33424 KB |
Output is correct |
51 |
Correct |
298 ms |
49124 KB |
Output is correct |
52 |
Correct |
404 ms |
48060 KB |
Output is correct |
53 |
Correct |
381 ms |
47436 KB |
Output is correct |
54 |
Correct |
375 ms |
49872 KB |
Output is correct |
55 |
Correct |
413 ms |
49356 KB |
Output is correct |
56 |
Correct |
340 ms |
50912 KB |
Output is correct |
57 |
Correct |
313 ms |
50532 KB |
Output is correct |
58 |
Correct |
380 ms |
49460 KB |
Output is correct |
59 |
Correct |
275 ms |
46388 KB |
Output is correct |
60 |
Correct |
327 ms |
55008 KB |
Output is correct |
61 |
Correct |
426 ms |
48464 KB |
Output is correct |
62 |
Correct |
348 ms |
49888 KB |
Output is correct |
63 |
Correct |
314 ms |
49576 KB |
Output is correct |
64 |
Correct |
5 ms |
9684 KB |
Output is correct |
65 |
Correct |
156 ms |
60744 KB |
Output is correct |
66 |
Correct |
185 ms |
66412 KB |
Output is correct |
67 |
Correct |
8 ms |
10484 KB |
Output is correct |
68 |
Correct |
9 ms |
10480 KB |
Output is correct |
69 |
Correct |
9 ms |
10452 KB |
Output is correct |
70 |
Correct |
9 ms |
10452 KB |
Output is correct |
71 |
Correct |
9 ms |
10492 KB |
Output is correct |
72 |
Correct |
280 ms |
45412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9708 KB |
Output is correct |
2 |
Correct |
9 ms |
10488 KB |
Output is correct |
3 |
Correct |
10 ms |
10492 KB |
Output is correct |
4 |
Correct |
9 ms |
10540 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 |
8 ms |
10296 KB |
Output is correct |
9 |
Correct |
9 ms |
10452 KB |
Output is correct |
10 |
Correct |
6 ms |
9764 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
178 ms |
33308 KB |
Output is correct |
13 |
Correct |
310 ms |
49036 KB |
Output is correct |
14 |
Correct |
307 ms |
45592 KB |
Output is correct |
15 |
Correct |
310 ms |
49396 KB |
Output is correct |
16 |
Correct |
319 ms |
49936 KB |
Output is correct |
17 |
Correct |
309 ms |
49924 KB |
Output is correct |
18 |
Correct |
5 ms |
9708 KB |
Output is correct |
19 |
Correct |
249 ms |
45304 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
144 ms |
57308 KB |
Output is correct |
22 |
Correct |
160 ms |
63016 KB |
Output is correct |
23 |
Correct |
175 ms |
66492 KB |
Output is correct |
24 |
Correct |
183 ms |
66408 KB |
Output is correct |
25 |
Correct |
8 ms |
10656 KB |
Output is correct |
26 |
Correct |
9 ms |
10856 KB |
Output is correct |
27 |
Correct |
7 ms |
10708 KB |
Output is correct |
28 |
Correct |
5 ms |
9684 KB |
Output is correct |
29 |
Correct |
5 ms |
9812 KB |
Output is correct |
30 |
Correct |
6 ms |
9812 KB |
Output is correct |
31 |
Correct |
107 ms |
43528 KB |
Output is correct |
32 |
Correct |
174 ms |
66292 KB |
Output is correct |
33 |
Correct |
5 ms |
9708 KB |
Output is correct |
34 |
Correct |
150 ms |
60788 KB |
Output is correct |
35 |
Correct |
167 ms |
66292 KB |
Output is correct |
36 |
Correct |
5 ms |
9684 KB |
Output is correct |
37 |
Correct |
7 ms |
9624 KB |
Output is correct |
38 |
Correct |
5 ms |
9684 KB |
Output is correct |
39 |
Correct |
5 ms |
9708 KB |
Output is correct |
40 |
Correct |
6 ms |
9760 KB |
Output is correct |
41 |
Correct |
6 ms |
9784 KB |
Output is correct |
42 |
Correct |
6 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 |
9756 KB |
Output is correct |
46 |
Correct |
6 ms |
9812 KB |
Output is correct |
47 |
Correct |
7 ms |
9812 KB |
Output is correct |
48 |
Correct |
6 ms |
9684 KB |
Output is correct |
49 |
Correct |
6 ms |
9712 KB |
Output is correct |
50 |
Correct |
6 ms |
9704 KB |
Output is correct |
51 |
Correct |
5 ms |
9704 KB |
Output is correct |
52 |
Correct |
5 ms |
9704 KB |
Output is correct |
53 |
Correct |
7 ms |
9692 KB |
Output is correct |
54 |
Correct |
5 ms |
9684 KB |
Output is correct |
55 |
Correct |
6 ms |
9720 KB |
Output is correct |
56 |
Correct |
5 ms |
9640 KB |
Output is correct |
57 |
Correct |
5 ms |
9684 KB |
Output is correct |
58 |
Correct |
7 ms |
10196 KB |
Output is correct |
59 |
Correct |
10 ms |
10612 KB |
Output is correct |
60 |
Correct |
9 ms |
10360 KB |
Output is correct |
61 |
Correct |
10 ms |
10452 KB |
Output is correct |
62 |
Correct |
11 ms |
10424 KB |
Output is correct |
63 |
Correct |
9 ms |
10452 KB |
Output is correct |
64 |
Correct |
9 ms |
10452 KB |
Output is correct |
65 |
Correct |
9 ms |
10452 KB |
Output is correct |
66 |
Correct |
9 ms |
10468 KB |
Output is correct |
67 |
Correct |
9 ms |
10452 KB |
Output is correct |
68 |
Correct |
9 ms |
10592 KB |
Output is correct |
69 |
Correct |
8 ms |
10836 KB |
Output is correct |
70 |
Correct |
8 ms |
10740 KB |
Output is correct |
71 |
Correct |
10 ms |
10452 KB |
Output is correct |
72 |
Correct |
11 ms |
10656 KB |
Output is correct |
73 |
Correct |
11 ms |
10452 KB |
Output is correct |
74 |
Correct |
5 ms |
9684 KB |
Output is correct |
75 |
Correct |
6 ms |
9684 KB |
Output is correct |
76 |
Correct |
5 ms |
9684 KB |
Output is correct |
77 |
Correct |
6 ms |
9716 KB |
Output is correct |
78 |
Correct |
6 ms |
9684 KB |
Output is correct |
79 |
Correct |
6 ms |
9684 KB |
Output is correct |
80 |
Correct |
5 ms |
9684 KB |
Output is correct |
81 |
Correct |
6 ms |
9684 KB |
Output is correct |
82 |
Correct |
6 ms |
9684 KB |
Output is correct |
83 |
Correct |
6 ms |
9812 KB |
Output is correct |
84 |
Correct |
6 ms |
9812 KB |
Output is correct |
85 |
Correct |
6 ms |
9660 KB |
Output is correct |
86 |
Correct |
6 ms |
9712 KB |
Output is correct |
87 |
Correct |
6 ms |
9684 KB |
Output is correct |
88 |
Correct |
8 ms |
10228 KB |
Output is correct |
89 |
Correct |
9 ms |
10452 KB |
Output is correct |
90 |
Correct |
9 ms |
10452 KB |
Output is correct |
91 |
Correct |
8 ms |
10324 KB |
Output is correct |
92 |
Correct |
9 ms |
10388 KB |
Output is correct |
93 |
Correct |
6 ms |
9708 KB |
Output is correct |
94 |
Correct |
6 ms |
9684 KB |
Output is correct |
95 |
Correct |
6 ms |
9704 KB |
Output is correct |
96 |
Correct |
5 ms |
9684 KB |
Output is correct |
97 |
Correct |
5 ms |
9684 KB |
Output is correct |
98 |
Correct |
5 ms |
9684 KB |
Output is correct |
99 |
Correct |
9 ms |
10452 KB |
Output is correct |
100 |
Correct |
9 ms |
10392 KB |
Output is correct |
101 |
Correct |
10 ms |
10452 KB |
Output is correct |
102 |
Correct |
9 ms |
10452 KB |
Output is correct |
103 |
Correct |
9 ms |
10452 KB |
Output is correct |
104 |
Correct |
402 ms |
48184 KB |
Output is correct |
105 |
Correct |
426 ms |
47484 KB |
Output is correct |
106 |
Correct |
345 ms |
49944 KB |
Output is correct |
107 |
Correct |
422 ms |
49396 KB |
Output is correct |
108 |
Correct |
321 ms |
50852 KB |
Output is correct |
109 |
Correct |
316 ms |
50336 KB |
Output is correct |
110 |
Correct |
397 ms |
49400 KB |
Output is correct |
111 |
Correct |
266 ms |
46408 KB |
Output is correct |
112 |
Correct |
333 ms |
54932 KB |
Output is correct |
113 |
Correct |
398 ms |
48328 KB |
Output is correct |
114 |
Correct |
338 ms |
49872 KB |
Output is correct |
115 |
Correct |
296 ms |
49568 KB |
Output is correct |
116 |
Correct |
5 ms |
9684 KB |
Output is correct |
117 |
Correct |
157 ms |
60796 KB |
Output is correct |
118 |
Correct |
182 ms |
66192 KB |
Output is correct |
119 |
Correct |
13 ms |
10452 KB |
Output is correct |
120 |
Correct |
10 ms |
10452 KB |
Output is correct |
121 |
Correct |
9 ms |
10452 KB |
Output is correct |
122 |
Correct |
9 ms |
10484 KB |
Output is correct |
123 |
Correct |
10 ms |
10520 KB |
Output is correct |
124 |
Correct |
253 ms |
45364 KB |
Output is correct |
125 |
Correct |
6 ms |
9684 KB |
Output is correct |
126 |
Correct |
6 ms |
9656 KB |
Output is correct |
127 |
Correct |
5 ms |
9684 KB |
Output is correct |
128 |
Correct |
344 ms |
43628 KB |
Output is correct |
129 |
Correct |
305 ms |
40368 KB |
Output is correct |
130 |
Correct |
417 ms |
49480 KB |
Output is correct |
131 |
Correct |
357 ms |
49784 KB |
Output is correct |
132 |
Correct |
343 ms |
47668 KB |
Output is correct |
133 |
Correct |
316 ms |
48816 KB |
Output is correct |
134 |
Correct |
327 ms |
48968 KB |
Output is correct |
135 |
Correct |
426 ms |
46140 KB |
Output is correct |
136 |
Correct |
318 ms |
47328 KB |
Output is correct |
137 |
Correct |
413 ms |
49456 KB |
Output is correct |
138 |
Correct |
379 ms |
59088 KB |
Output is correct |
139 |
Correct |
348 ms |
49848 KB |
Output is correct |
140 |
Correct |
307 ms |
49580 KB |
Output is correct |
141 |
Correct |
96 ms |
43472 KB |
Output is correct |
142 |
Correct |
172 ms |
66252 KB |
Output is correct |
143 |
Correct |
10 ms |
10324 KB |
Output is correct |
144 |
Correct |
10 ms |
10484 KB |
Output is correct |
145 |
Correct |
9 ms |
10504 KB |
Output is correct |
146 |
Correct |
8 ms |
10264 KB |
Output is correct |
147 |
Correct |
8 ms |
10452 KB |
Output is correct |
148 |
Correct |
6 ms |
9812 KB |
Output is correct |
149 |
Correct |
5 ms |
9704 KB |
Output is correct |
150 |
Correct |
6 ms |
9736 KB |
Output is correct |
151 |
Correct |
7 ms |
9684 KB |
Output is correct |
152 |
Correct |
5 ms |
9720 KB |
Output is correct |
153 |
Correct |
178 ms |
33424 KB |
Output is correct |
154 |
Correct |
298 ms |
49124 KB |
Output is correct |
155 |
Correct |
404 ms |
48060 KB |
Output is correct |
156 |
Correct |
381 ms |
47436 KB |
Output is correct |
157 |
Correct |
375 ms |
49872 KB |
Output is correct |
158 |
Correct |
413 ms |
49356 KB |
Output is correct |
159 |
Correct |
340 ms |
50912 KB |
Output is correct |
160 |
Correct |
313 ms |
50532 KB |
Output is correct |
161 |
Correct |
380 ms |
49460 KB |
Output is correct |
162 |
Correct |
275 ms |
46388 KB |
Output is correct |
163 |
Correct |
327 ms |
55008 KB |
Output is correct |
164 |
Correct |
426 ms |
48464 KB |
Output is correct |
165 |
Correct |
348 ms |
49888 KB |
Output is correct |
166 |
Correct |
314 ms |
49576 KB |
Output is correct |
167 |
Correct |
5 ms |
9684 KB |
Output is correct |
168 |
Correct |
156 ms |
60744 KB |
Output is correct |
169 |
Correct |
185 ms |
66412 KB |
Output is correct |
170 |
Correct |
8 ms |
10484 KB |
Output is correct |
171 |
Correct |
9 ms |
10480 KB |
Output is correct |
172 |
Correct |
9 ms |
10452 KB |
Output is correct |
173 |
Correct |
9 ms |
10452 KB |
Output is correct |
174 |
Correct |
9 ms |
10492 KB |
Output is correct |
175 |
Correct |
280 ms |
45412 KB |
Output is correct |
176 |
Correct |
5 ms |
9684 KB |
Output is correct |
177 |
Correct |
435 ms |
49692 KB |
Output is correct |
178 |
Correct |
322 ms |
40924 KB |
Output is correct |
179 |
Correct |
358 ms |
49888 KB |
Output is correct |
180 |
Correct |
351 ms |
49188 KB |
Output is correct |
181 |
Correct |
350 ms |
51904 KB |
Output is correct |
182 |
Correct |
340 ms |
51052 KB |
Output is correct |
183 |
Correct |
434 ms |
49460 KB |
Output is correct |
184 |
Correct |
316 ms |
48528 KB |
Output is correct |
185 |
Correct |
353 ms |
48696 KB |
Output is correct |
186 |
Correct |
317 ms |
47136 KB |
Output is correct |
187 |
Correct |
331 ms |
50112 KB |
Output is correct |
188 |
Correct |
422 ms |
47540 KB |
Output is correct |
189 |
Correct |
426 ms |
47256 KB |
Output is correct |
190 |
Correct |
382 ms |
50820 KB |
Output is correct |
191 |
Correct |
368 ms |
49884 KB |
Output is correct |
192 |
Correct |
367 ms |
50356 KB |
Output is correct |
193 |
Correct |
387 ms |
50344 KB |
Output is correct |
194 |
Correct |
372 ms |
50768 KB |
Output is correct |
195 |
Correct |
147 ms |
57540 KB |
Output is correct |
196 |
Correct |
170 ms |
63408 KB |
Output is correct |
197 |
Correct |
174 ms |
67088 KB |
Output is correct |
198 |
Correct |
175 ms |
67184 KB |
Output is correct |
199 |
Correct |
8 ms |
10196 KB |
Output is correct |
200 |
Correct |
9 ms |
10480 KB |
Output is correct |
201 |
Correct |
9 ms |
10336 KB |
Output is correct |
202 |
Correct |
9 ms |
10452 KB |
Output is correct |
203 |
Correct |
9 ms |
10452 KB |
Output is correct |
204 |
Correct |
9 ms |
10392 KB |
Output is correct |
205 |
Correct |
9 ms |
10444 KB |
Output is correct |
206 |
Correct |
9 ms |
10484 KB |
Output is correct |
207 |
Correct |
9 ms |
10488 KB |
Output is correct |
208 |
Correct |
8 ms |
10452 KB |
Output is correct |
209 |
Correct |
8 ms |
10708 KB |
Output is correct |
210 |
Correct |
8 ms |
10740 KB |
Output is correct |
211 |
Correct |
8 ms |
10836 KB |
Output is correct |
212 |
Correct |
8 ms |
10484 KB |
Output is correct |
213 |
Correct |
10 ms |
10488 KB |
Output is correct |
214 |
Correct |
9 ms |
10500 KB |
Output is correct |
215 |
Correct |
5 ms |
9712 KB |
Output is correct |
216 |
Correct |
5 ms |
9684 KB |
Output is correct |
217 |
Correct |
5 ms |
9684 KB |
Output is correct |
218 |
Correct |
7 ms |
9684 KB |
Output is correct |
219 |
Correct |
5 ms |
9684 KB |
Output is correct |
220 |
Correct |
7 ms |
9684 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 |
9684 KB |
Output is correct |
224 |
Correct |
6 ms |
9708 KB |
Output is correct |
225 |
Correct |
5 ms |
9812 KB |
Output is correct |
226 |
Correct |
6 ms |
9708 KB |
Output is correct |
227 |
Correct |
7 ms |
9684 KB |
Output is correct |
228 |
Correct |
6 ms |
9684 KB |
Output is correct |
229 |
Correct |
365 ms |
43724 KB |
Output is correct |
230 |
Correct |
332 ms |
40504 KB |
Output is correct |
231 |
Correct |
445 ms |
49400 KB |
Output is correct |
232 |
Correct |
410 ms |
49996 KB |
Output is correct |
233 |
Correct |
347 ms |
47800 KB |
Output is correct |
234 |
Correct |
332 ms |
48916 KB |
Output is correct |
235 |
Correct |
342 ms |
49036 KB |
Output is correct |
236 |
Correct |
399 ms |
46096 KB |
Output is correct |
237 |
Correct |
266 ms |
47380 KB |
Output is correct |
238 |
Correct |
431 ms |
49472 KB |
Output is correct |
239 |
Correct |
425 ms |
59020 KB |
Output is correct |
240 |
Correct |
361 ms |
49900 KB |
Output is correct |
241 |
Correct |
319 ms |
49588 KB |
Output is correct |
242 |
Correct |
98 ms |
43564 KB |
Output is correct |
243 |
Correct |
172 ms |
66240 KB |
Output is correct |
244 |
Correct |
9 ms |
10324 KB |
Output is correct |
245 |
Correct |
10 ms |
10520 KB |
Output is correct |
246 |
Correct |
12 ms |
10492 KB |
Output is correct |
247 |
Correct |
8 ms |
10324 KB |
Output is correct |
248 |
Correct |
9 ms |
10484 KB |
Output is correct |
249 |
Correct |
5 ms |
9752 KB |
Output is correct |
250 |
Correct |
6 ms |
9684 KB |
Output is correct |
251 |
Correct |
5 ms |
9712 KB |
Output is correct |
252 |
Correct |
5 ms |
9684 KB |
Output is correct |
253 |
Correct |
5 ms |
9708 KB |
Output is correct |
254 |
Correct |
178 ms |
33424 KB |
Output is correct |
255 |
Correct |
302 ms |
49168 KB |
Output is correct |
256 |
Correct |
280 ms |
45760 KB |
Output is correct |
257 |
Correct |
321 ms |
49576 KB |
Output is correct |
258 |
Correct |
324 ms |
50192 KB |
Output is correct |
259 |
Correct |
296 ms |
50276 KB |
Output is correct |
260 |
Correct |
422 ms |
48016 KB |
Output is correct |
261 |
Correct |
399 ms |
47392 KB |
Output is correct |
262 |
Correct |
352 ms |
49804 KB |
Output is correct |
263 |
Correct |
430 ms |
49268 KB |
Output is correct |
264 |
Correct |
344 ms |
50804 KB |
Output is correct |
265 |
Correct |
297 ms |
50412 KB |
Output is correct |
266 |
Correct |
399 ms |
49492 KB |
Output is correct |
267 |
Correct |
258 ms |
46444 KB |
Output is correct |
268 |
Correct |
344 ms |
54992 KB |
Output is correct |
269 |
Correct |
419 ms |
48252 KB |
Output is correct |
270 |
Correct |
343 ms |
49864 KB |
Output is correct |
271 |
Correct |
331 ms |
49572 KB |
Output is correct |
272 |
Correct |
5 ms |
9684 KB |
Output is correct |
273 |
Correct |
152 ms |
60804 KB |
Output is correct |
274 |
Correct |
182 ms |
66284 KB |
Output is correct |
275 |
Correct |
10 ms |
10452 KB |
Output is correct |
276 |
Correct |
9 ms |
10452 KB |
Output is correct |
277 |
Correct |
9 ms |
10452 KB |
Output is correct |
278 |
Correct |
9 ms |
10412 KB |
Output is correct |
279 |
Correct |
9 ms |
10512 KB |
Output is correct |
280 |
Correct |
254 ms |
45364 KB |
Output is correct |