#include "roads.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define ve vector
#define vei vector<int>
#define vell vector<ll>
#define sz(x) ((int)x.size())
#define each(it, x) for (auto &it : x)
#define debug(x) cout << #x << " = " << x << "\n";
#define FU function
#define VO void
vell minimum_closure_costs(int N, vei U, vei V, vei W) {
int n = N;
assert(sz(U) == n - 1);
assert(sz(V) == n - 1);
assert(sz(W) == n - 1);
#ifdef ONPC
if (0) {
debug(n);
each(it, U) cout << it << " "; cout << "\n";
each(it, V) cout << it << " "; cout << "\n";
each(it, W) cout << it << " "; cout << "\n";
}
#endif
ve<ve<pii>> g(n);
for (int i = 0; i < n - 1; i++)
g[U[i]].pb({ V[i], W[i] }),
g[V[i]].pb({ U[i], W[i] });
vei ord, deg(n, 0), pap(n, -1), upp(n, 0);
for (int i = 0; i < n; i++) deg[i] = sz(g[i]);
vector<bool> vis(n, 0);
ord.push_back(0);
vis[0] = 1;
for (int i = 0; i < (int)ord.size(); i++)
{
int a = ord[i];
ve<pii> kids;
each(it, g[a])
{
int b = it.f, c = it.s;
if (vis[b]) continue;
pap[b] = a;
upp[b] = c;
vis[b] = 1;
ord.pb(b);
kids.pb({ b, c });
}
g[a] = kids;
}
assert((int)ord.size() == n);
reverse(all(ord));
vei loc(n);
for (int i = 0; i < n; i++) loc[ord[i]] = i;
for (int i = 0; i < n; i++)
sort(g[i].begin(), g[i].end(), [&](pair<int, int> i, pair<int, int> j) {return deg[i.first] > deg[j.first]; });
vector<vector<int>> devine(n);
for (int i = 0; i < n; i++)
{
devine[deg[i]].pb(i);
}
vell sol(n, 0);
vei verts;
vell dp0(n, 0), dp1(n, 0);
ll smsz = 0;
vector<ll> sui(n, 0);
vector<multiset<int>> gustav1(n), gustav2(n);
vector<ll> s1(n, 0);
for (int a = 0; a < n; a++) each(it, g[a]) sui[a] += it.second, gustav2[a].insert(-it.second);
auto mv12 = [&](int a)
{
assert(!gustav1[a].empty());
auto it = gustav1[a].end();
it--;
int x = *it;
gustav1[a].erase(it);
gustav2[a].insert(x);
s1[a] -= x;
};
auto mv21 = [&](int a)
{
assert(!gustav2[a].empty());
auto it = gustav2[a].begin();
int x = *it;
gustav2[a].erase(it);
gustav1[a].insert(x);
s1[a] += x;
};
for (int k = n - 1; k >= 0; k--)
{
each(x, devine[k])
{
verts.pb(x);
if (pap[x] != -1)
{
if (gustav1[pap[x]].find(-upp[x]) != gustav1[pap[x]].end())
{
s1[pap[x]] -= (-upp[x]);
gustav1[pap[x]].erase(gustav1[pap[x]].find(-upp[x]));
}
else
if (gustav2[pap[x]].find(-upp[x]) != gustav2[pap[x]].end())
{
gustav2[pap[x]].erase(gustav2[pap[x]].find(-upp[x]));
}
else assert(0);
sui[pap[x]] -= upp[x];
}
}
smsz += sz(verts);
sort(all(verts), [&](int a, int b) {return loc[a] < loc[b]; });
// 0 => are gradul <= k + 0
// 1 => are gradul <= k + 1
ll print = 0;
each(a, verts)
{
assert(deg[a] >= k);
each(rem, vei({ k - 1, k }))
{
// sterg muchia => dp1 + cost
// pastrez muchia => dp0
int total = sz(g[a]);
int pastrez = min(total, rem);
pastrez = max(pastrez, 0);
ll su = sui[a];
each(it, g[a]) if (deg[it.first] >= k) su += dp1[it.first] + it.second; else break;
vector<ll> difs;
each(it, g[a]) if (deg[it.first] >= k) difs.pb(min(0LL, dp0[it.first] - dp1[it.first] - it.second)); else break;
auto iter = gustav1[a].begin();
sort(difs.begin(), difs.end());
int po = 0;
ll best = (ll)1e18;
ll cur = 0;
assert((int)difs.size() + (int)gustav1[a].size() + (int)gustav2[a].size() >= pastrez);
for (int take = 0; take <= pastrez; take++)
{
if (take > (int)difs.size()) break;
if (take)
{
cur += difs[take - 1];
}
int from_gustav = pastrez - take;
if (from_gustav <= (int)gustav1[a].size() + (int)gustav2[a].size())
{
while ((int)gustav1[a].size() < from_gustav) mv21(a);
while ((int)gustav1[a].size() > from_gustav) mv12(a);
assert((int)gustav1[a].size() == from_gustav);
best = min(best, cur + s1[a]);
}
}
su += best;
if (rem == k - 1) dp0[a] = su; else dp1[a] = su;
}
if (a == 0)
{
print += dp1[a];
}
else
{
if (deg[pap[a]] < k)
{
print += min(dp0[a], dp1[a] + upp[a]);
}
}
assert(dp0[a] >= dp1[a]);
}
sol[k] = print;
}
assert(smsz <= 3 * n);
return sol;
}
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:179:22: warning: variable 'iter' set but not used [-Wunused-but-set-variable]
179 | auto iter = gustav1[a].begin();
| ^~~~
roads.cpp:182:21: warning: unused variable 'po' [-Wunused-variable]
182 | int po = 0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
4 ms |
852 KB |
Output is correct |
3 |
Correct |
4 ms |
852 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
852 KB |
Output is correct |
9 |
Correct |
3 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
112 ms |
19172 KB |
Output is correct |
13 |
Correct |
215 ms |
32788 KB |
Output is correct |
14 |
Correct |
243 ms |
30724 KB |
Output is correct |
15 |
Correct |
286 ms |
33928 KB |
Output is correct |
16 |
Correct |
271 ms |
34452 KB |
Output is correct |
17 |
Correct |
210 ms |
33592 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
191 ms |
29584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
101 ms |
25712 KB |
Output is correct |
3 |
Correct |
103 ms |
28916 KB |
Output is correct |
4 |
Correct |
111 ms |
30848 KB |
Output is correct |
5 |
Correct |
110 ms |
30820 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
80 ms |
18564 KB |
Output is correct |
13 |
Correct |
138 ms |
30868 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
95 ms |
27804 KB |
Output is correct |
16 |
Correct |
110 ms |
30800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
276 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
276 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
3 ms |
852 KB |
Output is correct |
25 |
Correct |
3 ms |
852 KB |
Output is correct |
26 |
Correct |
4 ms |
852 KB |
Output is correct |
27 |
Correct |
4 ms |
864 KB |
Output is correct |
28 |
Correct |
4 ms |
852 KB |
Output is correct |
29 |
Correct |
3 ms |
852 KB |
Output is correct |
30 |
Correct |
5 ms |
852 KB |
Output is correct |
31 |
Correct |
4 ms |
852 KB |
Output is correct |
32 |
Correct |
3 ms |
852 KB |
Output is correct |
33 |
Correct |
2 ms |
724 KB |
Output is correct |
34 |
Correct |
3 ms |
852 KB |
Output is correct |
35 |
Correct |
3 ms |
724 KB |
Output is correct |
36 |
Correct |
4 ms |
852 KB |
Output is correct |
37 |
Correct |
5 ms |
852 KB |
Output is correct |
38 |
Correct |
3 ms |
852 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
1 ms |
340 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
0 ms |
340 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
1 ms |
340 KB |
Output is correct |
50 |
Correct |
1 ms |
340 KB |
Output is correct |
51 |
Correct |
1 ms |
340 KB |
Output is correct |
52 |
Correct |
1 ms |
352 KB |
Output is correct |
53 |
Correct |
4 ms |
724 KB |
Output is correct |
54 |
Correct |
4 ms |
852 KB |
Output is correct |
55 |
Correct |
5 ms |
852 KB |
Output is correct |
56 |
Correct |
4 ms |
724 KB |
Output is correct |
57 |
Correct |
4 ms |
852 KB |
Output is correct |
58 |
Correct |
1 ms |
212 KB |
Output is correct |
59 |
Correct |
1 ms |
340 KB |
Output is correct |
60 |
Correct |
1 ms |
340 KB |
Output is correct |
61 |
Correct |
1 ms |
340 KB |
Output is correct |
62 |
Correct |
1 ms |
340 KB |
Output is correct |
63 |
Correct |
0 ms |
212 KB |
Output is correct |
64 |
Correct |
3 ms |
852 KB |
Output is correct |
65 |
Correct |
3 ms |
852 KB |
Output is correct |
66 |
Correct |
3 ms |
852 KB |
Output is correct |
67 |
Correct |
3 ms |
852 KB |
Output is correct |
68 |
Correct |
3 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
31148 KB |
Output is correct |
2 |
Correct |
248 ms |
30596 KB |
Output is correct |
3 |
Correct |
238 ms |
32856 KB |
Output is correct |
4 |
Correct |
272 ms |
32152 KB |
Output is correct |
5 |
Correct |
196 ms |
32840 KB |
Output is correct |
6 |
Correct |
224 ms |
32420 KB |
Output is correct |
7 |
Correct |
237 ms |
32468 KB |
Output is correct |
8 |
Correct |
174 ms |
29280 KB |
Output is correct |
9 |
Correct |
268 ms |
31016 KB |
Output is correct |
10 |
Correct |
247 ms |
32836 KB |
Output is correct |
11 |
Correct |
248 ms |
34104 KB |
Output is correct |
12 |
Correct |
208 ms |
34048 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
111 ms |
28968 KB |
Output is correct |
15 |
Correct |
130 ms |
32172 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
4 ms |
852 KB |
Output is correct |
18 |
Correct |
4 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
852 KB |
Output is correct |
20 |
Correct |
4 ms |
980 KB |
Output is correct |
21 |
Correct |
172 ms |
29672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
31148 KB |
Output is correct |
2 |
Correct |
248 ms |
30596 KB |
Output is correct |
3 |
Correct |
238 ms |
32856 KB |
Output is correct |
4 |
Correct |
272 ms |
32152 KB |
Output is correct |
5 |
Correct |
196 ms |
32840 KB |
Output is correct |
6 |
Correct |
224 ms |
32420 KB |
Output is correct |
7 |
Correct |
237 ms |
32468 KB |
Output is correct |
8 |
Correct |
174 ms |
29280 KB |
Output is correct |
9 |
Correct |
268 ms |
31016 KB |
Output is correct |
10 |
Correct |
247 ms |
32836 KB |
Output is correct |
11 |
Correct |
248 ms |
34104 KB |
Output is correct |
12 |
Correct |
208 ms |
34048 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
111 ms |
28968 KB |
Output is correct |
15 |
Correct |
130 ms |
32172 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
4 ms |
852 KB |
Output is correct |
18 |
Correct |
4 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
852 KB |
Output is correct |
20 |
Correct |
4 ms |
980 KB |
Output is correct |
21 |
Correct |
172 ms |
29672 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
205 ms |
28876 KB |
Output is correct |
26 |
Correct |
180 ms |
26236 KB |
Output is correct |
27 |
Correct |
289 ms |
33576 KB |
Output is correct |
28 |
Correct |
244 ms |
34252 KB |
Output is correct |
29 |
Correct |
201 ms |
31600 KB |
Output is correct |
30 |
Correct |
242 ms |
32552 KB |
Output is correct |
31 |
Correct |
242 ms |
33376 KB |
Output is correct |
32 |
Correct |
235 ms |
30968 KB |
Output is correct |
33 |
Correct |
184 ms |
31400 KB |
Output is correct |
34 |
Correct |
247 ms |
33708 KB |
Output is correct |
35 |
Correct |
234 ms |
33684 KB |
Output is correct |
36 |
Correct |
248 ms |
34128 KB |
Output is correct |
37 |
Correct |
221 ms |
33940 KB |
Output is correct |
38 |
Correct |
62 ms |
19356 KB |
Output is correct |
39 |
Correct |
111 ms |
32160 KB |
Output is correct |
40 |
Correct |
3 ms |
724 KB |
Output is correct |
41 |
Correct |
3 ms |
852 KB |
Output is correct |
42 |
Correct |
4 ms |
980 KB |
Output is correct |
43 |
Correct |
3 ms |
852 KB |
Output is correct |
44 |
Correct |
4 ms |
920 KB |
Output is correct |
45 |
Correct |
1 ms |
212 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
1 ms |
296 KB |
Output is correct |
50 |
Correct |
116 ms |
19700 KB |
Output is correct |
51 |
Correct |
230 ms |
32788 KB |
Output is correct |
52 |
Correct |
256 ms |
32436 KB |
Output is correct |
53 |
Correct |
258 ms |
32036 KB |
Output is correct |
54 |
Correct |
245 ms |
34284 KB |
Output is correct |
55 |
Correct |
246 ms |
33516 KB |
Output is correct |
56 |
Correct |
210 ms |
34256 KB |
Output is correct |
57 |
Correct |
219 ms |
33800 KB |
Output is correct |
58 |
Correct |
231 ms |
33828 KB |
Output is correct |
59 |
Correct |
183 ms |
30580 KB |
Output is correct |
60 |
Correct |
210 ms |
31020 KB |
Output is correct |
61 |
Correct |
243 ms |
32840 KB |
Output is correct |
62 |
Correct |
229 ms |
34108 KB |
Output is correct |
63 |
Correct |
222 ms |
34052 KB |
Output is correct |
64 |
Correct |
1 ms |
212 KB |
Output is correct |
65 |
Correct |
105 ms |
29024 KB |
Output is correct |
66 |
Correct |
109 ms |
32208 KB |
Output is correct |
67 |
Correct |
3 ms |
852 KB |
Output is correct |
68 |
Correct |
3 ms |
852 KB |
Output is correct |
69 |
Correct |
3 ms |
960 KB |
Output is correct |
70 |
Correct |
3 ms |
852 KB |
Output is correct |
71 |
Correct |
4 ms |
980 KB |
Output is correct |
72 |
Correct |
177 ms |
29560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
4 ms |
852 KB |
Output is correct |
3 |
Correct |
4 ms |
852 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
852 KB |
Output is correct |
9 |
Correct |
3 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
112 ms |
19172 KB |
Output is correct |
13 |
Correct |
215 ms |
32788 KB |
Output is correct |
14 |
Correct |
243 ms |
30724 KB |
Output is correct |
15 |
Correct |
286 ms |
33928 KB |
Output is correct |
16 |
Correct |
271 ms |
34452 KB |
Output is correct |
17 |
Correct |
210 ms |
33592 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
191 ms |
29584 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
101 ms |
25712 KB |
Output is correct |
22 |
Correct |
103 ms |
28916 KB |
Output is correct |
23 |
Correct |
111 ms |
30848 KB |
Output is correct |
24 |
Correct |
110 ms |
30820 KB |
Output is correct |
25 |
Correct |
2 ms |
724 KB |
Output is correct |
26 |
Correct |
2 ms |
852 KB |
Output is correct |
27 |
Correct |
2 ms |
724 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
80 ms |
18564 KB |
Output is correct |
32 |
Correct |
138 ms |
30868 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
95 ms |
27804 KB |
Output is correct |
35 |
Correct |
110 ms |
30800 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
276 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
1 ms |
340 KB |
Output is correct |
45 |
Correct |
0 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
1 ms |
340 KB |
Output is correct |
50 |
Correct |
1 ms |
340 KB |
Output is correct |
51 |
Correct |
0 ms |
212 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
1 ms |
340 KB |
Output is correct |
54 |
Correct |
1 ms |
340 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
0 ms |
212 KB |
Output is correct |
57 |
Correct |
1 ms |
212 KB |
Output is correct |
58 |
Correct |
2 ms |
596 KB |
Output is correct |
59 |
Correct |
3 ms |
852 KB |
Output is correct |
60 |
Correct |
3 ms |
852 KB |
Output is correct |
61 |
Correct |
4 ms |
852 KB |
Output is correct |
62 |
Correct |
4 ms |
864 KB |
Output is correct |
63 |
Correct |
4 ms |
852 KB |
Output is correct |
64 |
Correct |
3 ms |
852 KB |
Output is correct |
65 |
Correct |
5 ms |
852 KB |
Output is correct |
66 |
Correct |
4 ms |
852 KB |
Output is correct |
67 |
Correct |
3 ms |
852 KB |
Output is correct |
68 |
Correct |
2 ms |
724 KB |
Output is correct |
69 |
Correct |
3 ms |
852 KB |
Output is correct |
70 |
Correct |
3 ms |
724 KB |
Output is correct |
71 |
Correct |
4 ms |
852 KB |
Output is correct |
72 |
Correct |
5 ms |
852 KB |
Output is correct |
73 |
Correct |
3 ms |
852 KB |
Output is correct |
74 |
Correct |
1 ms |
212 KB |
Output is correct |
75 |
Correct |
0 ms |
212 KB |
Output is correct |
76 |
Correct |
1 ms |
340 KB |
Output is correct |
77 |
Correct |
1 ms |
340 KB |
Output is correct |
78 |
Correct |
1 ms |
340 KB |
Output is correct |
79 |
Correct |
1 ms |
340 KB |
Output is correct |
80 |
Correct |
1 ms |
340 KB |
Output is correct |
81 |
Correct |
1 ms |
340 KB |
Output is correct |
82 |
Correct |
0 ms |
340 KB |
Output is correct |
83 |
Correct |
1 ms |
340 KB |
Output is correct |
84 |
Correct |
1 ms |
340 KB |
Output is correct |
85 |
Correct |
1 ms |
340 KB |
Output is correct |
86 |
Correct |
1 ms |
340 KB |
Output is correct |
87 |
Correct |
1 ms |
352 KB |
Output is correct |
88 |
Correct |
4 ms |
724 KB |
Output is correct |
89 |
Correct |
4 ms |
852 KB |
Output is correct |
90 |
Correct |
5 ms |
852 KB |
Output is correct |
91 |
Correct |
4 ms |
724 KB |
Output is correct |
92 |
Correct |
4 ms |
852 KB |
Output is correct |
93 |
Correct |
1 ms |
212 KB |
Output is correct |
94 |
Correct |
1 ms |
340 KB |
Output is correct |
95 |
Correct |
1 ms |
340 KB |
Output is correct |
96 |
Correct |
1 ms |
340 KB |
Output is correct |
97 |
Correct |
1 ms |
340 KB |
Output is correct |
98 |
Correct |
0 ms |
212 KB |
Output is correct |
99 |
Correct |
3 ms |
852 KB |
Output is correct |
100 |
Correct |
3 ms |
852 KB |
Output is correct |
101 |
Correct |
3 ms |
852 KB |
Output is correct |
102 |
Correct |
3 ms |
852 KB |
Output is correct |
103 |
Correct |
3 ms |
852 KB |
Output is correct |
104 |
Correct |
248 ms |
31148 KB |
Output is correct |
105 |
Correct |
248 ms |
30596 KB |
Output is correct |
106 |
Correct |
238 ms |
32856 KB |
Output is correct |
107 |
Correct |
272 ms |
32152 KB |
Output is correct |
108 |
Correct |
196 ms |
32840 KB |
Output is correct |
109 |
Correct |
224 ms |
32420 KB |
Output is correct |
110 |
Correct |
237 ms |
32468 KB |
Output is correct |
111 |
Correct |
174 ms |
29280 KB |
Output is correct |
112 |
Correct |
268 ms |
31016 KB |
Output is correct |
113 |
Correct |
247 ms |
32836 KB |
Output is correct |
114 |
Correct |
248 ms |
34104 KB |
Output is correct |
115 |
Correct |
208 ms |
34048 KB |
Output is correct |
116 |
Correct |
1 ms |
212 KB |
Output is correct |
117 |
Correct |
111 ms |
28968 KB |
Output is correct |
118 |
Correct |
130 ms |
32172 KB |
Output is correct |
119 |
Correct |
3 ms |
852 KB |
Output is correct |
120 |
Correct |
4 ms |
852 KB |
Output is correct |
121 |
Correct |
4 ms |
852 KB |
Output is correct |
122 |
Correct |
3 ms |
852 KB |
Output is correct |
123 |
Correct |
4 ms |
980 KB |
Output is correct |
124 |
Correct |
172 ms |
29672 KB |
Output is correct |
125 |
Correct |
1 ms |
212 KB |
Output is correct |
126 |
Correct |
1 ms |
212 KB |
Output is correct |
127 |
Correct |
1 ms |
212 KB |
Output is correct |
128 |
Correct |
205 ms |
28876 KB |
Output is correct |
129 |
Correct |
180 ms |
26236 KB |
Output is correct |
130 |
Correct |
289 ms |
33576 KB |
Output is correct |
131 |
Correct |
244 ms |
34252 KB |
Output is correct |
132 |
Correct |
201 ms |
31600 KB |
Output is correct |
133 |
Correct |
242 ms |
32552 KB |
Output is correct |
134 |
Correct |
242 ms |
33376 KB |
Output is correct |
135 |
Correct |
235 ms |
30968 KB |
Output is correct |
136 |
Correct |
184 ms |
31400 KB |
Output is correct |
137 |
Correct |
247 ms |
33708 KB |
Output is correct |
138 |
Correct |
234 ms |
33684 KB |
Output is correct |
139 |
Correct |
248 ms |
34128 KB |
Output is correct |
140 |
Correct |
221 ms |
33940 KB |
Output is correct |
141 |
Correct |
62 ms |
19356 KB |
Output is correct |
142 |
Correct |
111 ms |
32160 KB |
Output is correct |
143 |
Correct |
3 ms |
724 KB |
Output is correct |
144 |
Correct |
3 ms |
852 KB |
Output is correct |
145 |
Correct |
4 ms |
980 KB |
Output is correct |
146 |
Correct |
3 ms |
852 KB |
Output is correct |
147 |
Correct |
4 ms |
920 KB |
Output is correct |
148 |
Correct |
1 ms |
212 KB |
Output is correct |
149 |
Correct |
1 ms |
340 KB |
Output is correct |
150 |
Correct |
1 ms |
340 KB |
Output is correct |
151 |
Correct |
1 ms |
340 KB |
Output is correct |
152 |
Correct |
1 ms |
296 KB |
Output is correct |
153 |
Correct |
116 ms |
19700 KB |
Output is correct |
154 |
Correct |
230 ms |
32788 KB |
Output is correct |
155 |
Correct |
256 ms |
32436 KB |
Output is correct |
156 |
Correct |
258 ms |
32036 KB |
Output is correct |
157 |
Correct |
245 ms |
34284 KB |
Output is correct |
158 |
Correct |
246 ms |
33516 KB |
Output is correct |
159 |
Correct |
210 ms |
34256 KB |
Output is correct |
160 |
Correct |
219 ms |
33800 KB |
Output is correct |
161 |
Correct |
231 ms |
33828 KB |
Output is correct |
162 |
Correct |
183 ms |
30580 KB |
Output is correct |
163 |
Correct |
210 ms |
31020 KB |
Output is correct |
164 |
Correct |
243 ms |
32840 KB |
Output is correct |
165 |
Correct |
229 ms |
34108 KB |
Output is correct |
166 |
Correct |
222 ms |
34052 KB |
Output is correct |
167 |
Correct |
1 ms |
212 KB |
Output is correct |
168 |
Correct |
105 ms |
29024 KB |
Output is correct |
169 |
Correct |
109 ms |
32208 KB |
Output is correct |
170 |
Correct |
3 ms |
852 KB |
Output is correct |
171 |
Correct |
3 ms |
852 KB |
Output is correct |
172 |
Correct |
3 ms |
960 KB |
Output is correct |
173 |
Correct |
3 ms |
852 KB |
Output is correct |
174 |
Correct |
4 ms |
980 KB |
Output is correct |
175 |
Correct |
177 ms |
29560 KB |
Output is correct |
176 |
Correct |
1 ms |
212 KB |
Output is correct |
177 |
Correct |
269 ms |
34012 KB |
Output is correct |
178 |
Correct |
183 ms |
26664 KB |
Output is correct |
179 |
Correct |
269 ms |
34396 KB |
Output is correct |
180 |
Correct |
236 ms |
32840 KB |
Output is correct |
181 |
Correct |
193 ms |
35120 KB |
Output is correct |
182 |
Correct |
224 ms |
34640 KB |
Output is correct |
183 |
Correct |
231 ms |
33996 KB |
Output is correct |
184 |
Correct |
252 ms |
32756 KB |
Output is correct |
185 |
Correct |
269 ms |
33252 KB |
Output is correct |
186 |
Correct |
254 ms |
31944 KB |
Output is correct |
187 |
Correct |
260 ms |
34560 KB |
Output is correct |
188 |
Correct |
238 ms |
32124 KB |
Output is correct |
189 |
Correct |
257 ms |
31960 KB |
Output is correct |
190 |
Correct |
248 ms |
34888 KB |
Output is correct |
191 |
Correct |
223 ms |
34056 KB |
Output is correct |
192 |
Correct |
262 ms |
34584 KB |
Output is correct |
193 |
Correct |
268 ms |
34672 KB |
Output is correct |
194 |
Correct |
225 ms |
34996 KB |
Output is correct |
195 |
Correct |
92 ms |
27364 KB |
Output is correct |
196 |
Correct |
104 ms |
30824 KB |
Output is correct |
197 |
Correct |
114 ms |
32976 KB |
Output is correct |
198 |
Correct |
109 ms |
32976 KB |
Output is correct |
199 |
Correct |
2 ms |
724 KB |
Output is correct |
200 |
Correct |
4 ms |
868 KB |
Output is correct |
201 |
Correct |
3 ms |
820 KB |
Output is correct |
202 |
Correct |
4 ms |
852 KB |
Output is correct |
203 |
Correct |
4 ms |
980 KB |
Output is correct |
204 |
Correct |
4 ms |
980 KB |
Output is correct |
205 |
Correct |
3 ms |
852 KB |
Output is correct |
206 |
Correct |
4 ms |
980 KB |
Output is correct |
207 |
Correct |
4 ms |
980 KB |
Output is correct |
208 |
Correct |
4 ms |
948 KB |
Output is correct |
209 |
Correct |
2 ms |
852 KB |
Output is correct |
210 |
Correct |
3 ms |
852 KB |
Output is correct |
211 |
Correct |
2 ms |
860 KB |
Output is correct |
212 |
Correct |
4 ms |
852 KB |
Output is correct |
213 |
Correct |
4 ms |
980 KB |
Output is correct |
214 |
Correct |
4 ms |
980 KB |
Output is correct |
215 |
Correct |
1 ms |
212 KB |
Output is correct |
216 |
Correct |
0 ms |
300 KB |
Output is correct |
217 |
Correct |
1 ms |
340 KB |
Output is correct |
218 |
Correct |
1 ms |
296 KB |
Output is correct |
219 |
Correct |
1 ms |
340 KB |
Output is correct |
220 |
Correct |
1 ms |
340 KB |
Output is correct |
221 |
Correct |
1 ms |
340 KB |
Output is correct |
222 |
Correct |
1 ms |
340 KB |
Output is correct |
223 |
Correct |
1 ms |
344 KB |
Output is correct |
224 |
Correct |
1 ms |
340 KB |
Output is correct |
225 |
Correct |
1 ms |
340 KB |
Output is correct |
226 |
Correct |
1 ms |
340 KB |
Output is correct |
227 |
Correct |
1 ms |
340 KB |
Output is correct |
228 |
Correct |
1 ms |
340 KB |
Output is correct |
229 |
Correct |
226 ms |
28816 KB |
Output is correct |
230 |
Correct |
180 ms |
26204 KB |
Output is correct |
231 |
Correct |
267 ms |
33460 KB |
Output is correct |
232 |
Correct |
270 ms |
34280 KB |
Output is correct |
233 |
Correct |
199 ms |
31548 KB |
Output is correct |
234 |
Correct |
257 ms |
32584 KB |
Output is correct |
235 |
Correct |
249 ms |
33324 KB |
Output is correct |
236 |
Correct |
229 ms |
30968 KB |
Output is correct |
237 |
Correct |
183 ms |
31316 KB |
Output is correct |
238 |
Correct |
244 ms |
33828 KB |
Output is correct |
239 |
Correct |
254 ms |
33680 KB |
Output is correct |
240 |
Correct |
247 ms |
34128 KB |
Output is correct |
241 |
Correct |
237 ms |
33936 KB |
Output is correct |
242 |
Correct |
63 ms |
19368 KB |
Output is correct |
243 |
Correct |
116 ms |
32168 KB |
Output is correct |
244 |
Correct |
3 ms |
820 KB |
Output is correct |
245 |
Correct |
4 ms |
980 KB |
Output is correct |
246 |
Correct |
4 ms |
952 KB |
Output is correct |
247 |
Correct |
3 ms |
852 KB |
Output is correct |
248 |
Correct |
3 ms |
852 KB |
Output is correct |
249 |
Correct |
1 ms |
300 KB |
Output is correct |
250 |
Correct |
1 ms |
340 KB |
Output is correct |
251 |
Correct |
1 ms |
340 KB |
Output is correct |
252 |
Correct |
1 ms |
340 KB |
Output is correct |
253 |
Correct |
1 ms |
340 KB |
Output is correct |
254 |
Correct |
114 ms |
19708 KB |
Output is correct |
255 |
Correct |
199 ms |
32784 KB |
Output is correct |
256 |
Correct |
222 ms |
30696 KB |
Output is correct |
257 |
Correct |
242 ms |
33936 KB |
Output is correct |
258 |
Correct |
244 ms |
34476 KB |
Output is correct |
259 |
Correct |
202 ms |
33584 KB |
Output is correct |
260 |
Correct |
231 ms |
32500 KB |
Output is correct |
261 |
Correct |
242 ms |
31936 KB |
Output is correct |
262 |
Correct |
222 ms |
34216 KB |
Output is correct |
263 |
Correct |
255 ms |
33460 KB |
Output is correct |
264 |
Correct |
190 ms |
34248 KB |
Output is correct |
265 |
Correct |
219 ms |
33764 KB |
Output is correct |
266 |
Correct |
221 ms |
33820 KB |
Output is correct |
267 |
Correct |
177 ms |
30724 KB |
Output is correct |
268 |
Correct |
211 ms |
31100 KB |
Output is correct |
269 |
Correct |
254 ms |
32828 KB |
Output is correct |
270 |
Correct |
221 ms |
34000 KB |
Output is correct |
271 |
Correct |
207 ms |
33980 KB |
Output is correct |
272 |
Correct |
0 ms |
212 KB |
Output is correct |
273 |
Correct |
100 ms |
29020 KB |
Output is correct |
274 |
Correct |
107 ms |
32128 KB |
Output is correct |
275 |
Correct |
3 ms |
852 KB |
Output is correct |
276 |
Correct |
3 ms |
952 KB |
Output is correct |
277 |
Correct |
4 ms |
856 KB |
Output is correct |
278 |
Correct |
4 ms |
852 KB |
Output is correct |
279 |
Correct |
4 ms |
980 KB |
Output is correct |
280 |
Correct |
175 ms |
29672 KB |
Output is correct |