// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "joitour.h"
using namespace std;
typedef long long ll;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
template <typename T = int>
struct StaticTopTree {
struct Path {
struct Mat {
ll ab, a, b, c;
void incre(ll x, ll y) {
ab += x * b + y * a + x * y * c;
a += x * c;
b += y * c;
}
Mat& operator+=(const Mat &o) {
ab += o.ab;
a += o.a;
b += o.b;
c += o.c;
return *this;
}
Mat operator+(const Mat &o) const {
Mat res = *this;
res += o;
return res;
}
};
ll c0, c2;
Mat mp, mu;
ll uc0, uc2;
};
struct Point {
ll c0, c2, c02, rp, ru, uc0, uc2;
};
Path initVertex(int u) {
if (a[u] == 1) {
typename Path::Mat m = {0, 0, 0, 1};
return {0, 0, m, m, 0, 0};
} else {
bool b0 = a[u] == 0, b2 = a[u] == 2;
typename Path::Mat m = {0, 0, 0, 0};
return {b0, b2, m, m, 0, 0};
}
}
Path addVertex(int u, Point x) {
if (a[u] == 1) {
return {x.c0, x.c2,
{x.rp + x.c02, 0, 0, 1},
{x.ru + x.c0 * x.c2, x.c0, x.c2, 1},
x.uc0, x.uc2};
} else {
int c0 = x.c0 + (a[u] == 0), c2 = x.c2 + (a[u] == 2);
return {c0, c2, {x.rp, 0, 0, 0}, {x.ru, 0, 0, 0}, x.uc0, x.uc2};
}
}
Point addEdge(Path x) {
return {x.c0, x.c2, x.c0 * x.c2, x.mp.ab, x.mu.ab,
x.uc0 + x.mu.a, x.uc2 + x.mu.b};
}
Path compress(Path lx, Path rx) {
lx.c0 += rx.c0;
lx.c2 += rx.c2;
lx.mp.incre(rx.c0, rx.c2);
lx.mu.incre(rx.c0, rx.c2);
lx.mp += rx.mp;
lx.mu += rx.mu;
lx.uc0 += rx.uc0;
lx.uc2 += rx.uc2;
return lx;
}
Point rake(Point lx, Point rx) {
return {lx.c0 + rx.c0, lx.c2 + rx.c2, lx.c02 + rx.c02, lx.rp + rx.rp, lx.ru + rx.ru, lx.uc0 + rx.uc0, lx.uc2 + rx.uc2};
}
StaticTopTree() {}
StaticTopTree(int n, vector<vector<int>> &adj): n(n), adj(adj) {
lc.resize(4 * n + 5);
rc.resize(4 * n + 5);
p.resize(4 * n + 5);
op.resize(4 * n + 5);
path.resize(4 * n + 5);
point.resize(4 * n + 5);
ptr = n + 1;
hld(1, -1);
r = buildPath(1).first;
}
void init(vector<T> &_a) {
a = _a;
dfs(r);
}
void update(int u, T &x) {
a[u] = x;
apply(u);
while (p[u]) {
u = p[u];
apply(u);
}
}
Path query(int u) {
Path res = path[u];
while (p[u]) {
if (op[p[u]] == AddEdge) {
break;
}
if (lc[p[u]] == u) {
res = compress(res, path[rc[p[u]]]);
}
u = p[u];
}
return res;
}
private:
enum Op {
InitVertex,
AddVertex,
AddEdge,
Compress,
Rake
};
int n;
vector<vector<int>> adj;
vector<T> a;
int r, ptr;
vector<int> lc, rc, p;
vector<Op> op;
vector<Path> path;
vector<Point> point;
int hld(int u, int p) {
int sub = 1, mx = 0;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (v == p) {
adj[u].erase(adj[u].begin() + i);
i--;
continue;
}
int vsub = hld(v, u);
sub += vsub;
if (vsub > mx) {
mx = vsub;
if (i) {
swap(adj[u][i], adj[u][0]);
}
}
}
return sub;
}
void dfs(int u) {
if (lc[u]) {
dfs(lc[u]);
}
if (rc[u]) {
dfs(rc[u]);
}
apply(u);
}
void apply(int u) {
if (op[u] == InitVertex) {
path[u] = initVertex(u);
} else if (op[u] == AddVertex) {
path[u] = addVertex(u, point[lc[u]]);
} else if (op[u] == AddEdge) {
point[u] = addEdge(path[lc[u]]);
} else if (op[u] == Compress) {
path[u] = compress(path[lc[u]], path[rc[u]]);
} else if (op[u] == Rake) {
point[u] = rake(point[lc[u]], point[rc[u]]);
}
}
inline void add(int u, int l, int r, Op o) {
lc[u] = l; p[l] = u;
rc[u] = r; p[r] = u;
op[u] = o;
}
pair<int, int> merge(vector<pair<int, int>> &lst, Op o) {
if (lst.size() == 1) {
return lst[0];
}
int tot = 0;
for (auto [u, s] : lst) {
tot += s;
}
vector<pair<int, int>> lft, rht;
for (auto [u, s] : lst) {
(tot > s ? lft : rht).push_back({u, s});
tot -= 2 * s;
}
auto [lu, ls] = merge(lft, o);
auto [ru, rs] = merge(rht, o);
add(ptr, lu, ru, o);
return {ptr++, ls + rs + 1};
}
pair<int, int> buildPath(int u) {
vector<pair<int, int>> lst;
lst.push_back(buildVertex(u));
while (!adj[u].empty()) {
u = adj[u][0];
lst.push_back(buildVertex(u));
}
return merge(lst, Compress);
}
pair<int, int> buildVertex(int u) {
if (adj[u].size() <= 1) {
op[u] = InitVertex;
return {u, 1};
}
vector<pair<int, int>> lst;
for (int i = 1; i < adj[u].size(); i++) {
lst.push_back(buildEdge(adj[u][i]));
}
auto [v, s] = merge(lst, Rake);
add(u, v, 0, AddVertex);
return {u, s + 1};
}
pair<int, int> buildEdge(int u) {
auto [v, s] = buildPath(u);
add(ptr, v, 0, AddEdge);
return {ptr++, s + 1};
}
};
int n;
vector<int> a;
vector<vector<int>> adj;
StaticTopTree stt;
ll c[3];
void init(int N, vector<int> F, vector<int> U, vector<int> V, int Q) {
n = N;
a.resize(n + 1);
for (int i = 0; i < n; i++) {
a[i + 1] = F[i];
c[a[i + 1]]++;
}
adj.resize(n + 1);
for (int i = 0; i < n - 1; i++) {
adj[U[i] + 1].push_back(V[i] + 1);
adj[V[i] + 1].push_back(U[i] + 1);
}
stt = StaticTopTree(n, adj);
stt.init(a);
}
void change(int x, int y) {
x++;
c[a[x]]--;
a[x] = y;
c[a[x]]++;
stt.update(x, y);
}
// cnt0[1] * cnt1[1] * cnt2[1] - cnt0[u] * cnt2[u] * (f[p[u]] == 1) - (cnt0[1] - cnt0[u]) * (cnt2[1] - cnt2[u]) * (f[u] == 1)
ll num_tours() {
StaticTopTree<int>::Path res = stt.query(1);
return c[0] * c[1] * c[2] - res.mp.ab - (c[0] * c[1] * c[2] -
c[0] * (res.uc2 + res.mu.b) - c[2] * (res.uc0 + res.mu.a) +
res.mu.ab);
}
Compilation message
joitour.cpp: In instantiation of 'int StaticTopTree<T>::hld(int, int) [with T = int]':
joitour.cpp:94:9: required from 'StaticTopTree<T>::StaticTopTree(int, std::vector<std::vector<int> >&) [with T = int]'
joitour.cpp:250:31: required from here
joitour.cpp:140:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
joitour.cpp: In instantiation of 'std::pair<int, int> StaticTopTree<T>::buildVertex(int) [with T = int]':
joitour.cpp:205:23: required from 'std::pair<int, int> StaticTopTree<T>::buildPath(int) [with T = int]'
joitour.cpp:95:13: required from 'StaticTopTree<T>::StaticTopTree(int, std::vector<std::vector<int> >&) [with T = int]'
joitour.cpp:250:31: required from here
joitour.cpp:218:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | for (int i = 1; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
8 ms |
3928 KB |
Output is correct |
26 |
Correct |
8 ms |
3672 KB |
Output is correct |
27 |
Correct |
8 ms |
3756 KB |
Output is correct |
28 |
Correct |
8 ms |
3672 KB |
Output is correct |
29 |
Correct |
8 ms |
3672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
255 ms |
167856 KB |
Output is correct |
3 |
Correct |
211 ms |
167800 KB |
Output is correct |
4 |
Correct |
240 ms |
166228 KB |
Output is correct |
5 |
Correct |
213 ms |
168368 KB |
Output is correct |
6 |
Correct |
122 ms |
160232 KB |
Output is correct |
7 |
Correct |
116 ms |
160428 KB |
Output is correct |
8 |
Correct |
185 ms |
159952 KB |
Output is correct |
9 |
Correct |
175 ms |
159956 KB |
Output is correct |
10 |
Correct |
182 ms |
160316 KB |
Output is correct |
11 |
Correct |
176 ms |
160356 KB |
Output is correct |
12 |
Correct |
182 ms |
163108 KB |
Output is correct |
13 |
Correct |
212 ms |
163344 KB |
Output is correct |
14 |
Correct |
183 ms |
163140 KB |
Output is correct |
15 |
Correct |
202 ms |
162752 KB |
Output is correct |
16 |
Correct |
207 ms |
169992 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
344 KB |
Output is correct |
21 |
Correct |
181 ms |
160220 KB |
Output is correct |
22 |
Correct |
184 ms |
160232 KB |
Output is correct |
23 |
Correct |
179 ms |
160292 KB |
Output is correct |
24 |
Correct |
188 ms |
160216 KB |
Output is correct |
25 |
Correct |
186 ms |
165836 KB |
Output is correct |
26 |
Correct |
213 ms |
165832 KB |
Output is correct |
27 |
Correct |
180 ms |
166028 KB |
Output is correct |
28 |
Correct |
185 ms |
165848 KB |
Output is correct |
29 |
Correct |
144 ms |
171856 KB |
Output is correct |
30 |
Correct |
154 ms |
172056 KB |
Output is correct |
31 |
Correct |
144 ms |
171976 KB |
Output is correct |
32 |
Correct |
145 ms |
172048 KB |
Output is correct |
33 |
Correct |
127 ms |
160036 KB |
Output is correct |
34 |
Correct |
112 ms |
160144 KB |
Output is correct |
35 |
Correct |
119 ms |
159952 KB |
Output is correct |
36 |
Correct |
114 ms |
159956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
8 ms |
3928 KB |
Output is correct |
9 |
Correct |
139 ms |
171976 KB |
Output is correct |
10 |
Correct |
142 ms |
172004 KB |
Output is correct |
11 |
Correct |
140 ms |
171808 KB |
Output is correct |
12 |
Correct |
139 ms |
171980 KB |
Output is correct |
13 |
Correct |
226 ms |
86384 KB |
Output is correct |
14 |
Correct |
221 ms |
86188 KB |
Output is correct |
15 |
Correct |
245 ms |
86464 KB |
Output is correct |
16 |
Correct |
219 ms |
86188 KB |
Output is correct |
17 |
Correct |
224 ms |
86192 KB |
Output is correct |
18 |
Correct |
251 ms |
86076 KB |
Output is correct |
19 |
Correct |
447 ms |
171852 KB |
Output is correct |
20 |
Correct |
434 ms |
171872 KB |
Output is correct |
21 |
Correct |
506 ms |
172048 KB |
Output is correct |
22 |
Correct |
502 ms |
171856 KB |
Output is correct |
23 |
Correct |
486 ms |
171852 KB |
Output is correct |
24 |
Correct |
460 ms |
171856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
7 ms |
3672 KB |
Output is correct |
8 |
Correct |
110 ms |
160336 KB |
Output is correct |
9 |
Correct |
112 ms |
159952 KB |
Output is correct |
10 |
Correct |
110 ms |
160144 KB |
Output is correct |
11 |
Correct |
121 ms |
160224 KB |
Output is correct |
12 |
Correct |
211 ms |
80192 KB |
Output is correct |
13 |
Correct |
269 ms |
80188 KB |
Output is correct |
14 |
Correct |
244 ms |
80132 KB |
Output is correct |
15 |
Correct |
246 ms |
80196 KB |
Output is correct |
16 |
Correct |
254 ms |
80204 KB |
Output is correct |
17 |
Correct |
237 ms |
80048 KB |
Output is correct |
18 |
Correct |
400 ms |
160148 KB |
Output is correct |
19 |
Correct |
486 ms |
160132 KB |
Output is correct |
20 |
Correct |
435 ms |
159964 KB |
Output is correct |
21 |
Correct |
495 ms |
159956 KB |
Output is correct |
22 |
Correct |
487 ms |
159976 KB |
Output is correct |
23 |
Correct |
499 ms |
160316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
8 ms |
3928 KB |
Output is correct |
26 |
Correct |
8 ms |
3672 KB |
Output is correct |
27 |
Correct |
8 ms |
3756 KB |
Output is correct |
28 |
Correct |
8 ms |
3672 KB |
Output is correct |
29 |
Correct |
8 ms |
3672 KB |
Output is correct |
30 |
Correct |
223 ms |
82888 KB |
Output is correct |
31 |
Correct |
220 ms |
83552 KB |
Output is correct |
32 |
Correct |
242 ms |
83836 KB |
Output is correct |
33 |
Correct |
234 ms |
84288 KB |
Output is correct |
34 |
Correct |
249 ms |
84380 KB |
Output is correct |
35 |
Correct |
253 ms |
83660 KB |
Output is correct |
36 |
Correct |
244 ms |
80064 KB |
Output is correct |
37 |
Correct |
239 ms |
80076 KB |
Output is correct |
38 |
Correct |
266 ms |
80244 KB |
Output is correct |
39 |
Correct |
272 ms |
80276 KB |
Output is correct |
40 |
Correct |
273 ms |
80188 KB |
Output is correct |
41 |
Correct |
225 ms |
80448 KB |
Output is correct |
42 |
Correct |
242 ms |
81852 KB |
Output is correct |
43 |
Correct |
234 ms |
81448 KB |
Output is correct |
44 |
Correct |
264 ms |
81512 KB |
Output is correct |
45 |
Correct |
223 ms |
81836 KB |
Output is correct |
46 |
Correct |
253 ms |
81420 KB |
Output is correct |
47 |
Correct |
294 ms |
82048 KB |
Output is correct |
48 |
Correct |
226 ms |
83816 KB |
Output is correct |
49 |
Correct |
254 ms |
84992 KB |
Output is correct |
50 |
Correct |
248 ms |
83524 KB |
Output is correct |
51 |
Correct |
229 ms |
80188 KB |
Output is correct |
52 |
Correct |
261 ms |
80176 KB |
Output is correct |
53 |
Correct |
255 ms |
80212 KB |
Output is correct |
54 |
Correct |
237 ms |
80208 KB |
Output is correct |
55 |
Correct |
263 ms |
80192 KB |
Output is correct |
56 |
Correct |
227 ms |
80208 KB |
Output is correct |
57 |
Correct |
223 ms |
83012 KB |
Output is correct |
58 |
Correct |
236 ms |
83172 KB |
Output is correct |
59 |
Correct |
245 ms |
83004 KB |
Output is correct |
60 |
Correct |
246 ms |
83184 KB |
Output is correct |
61 |
Correct |
237 ms |
82996 KB |
Output is correct |
62 |
Correct |
216 ms |
86184 KB |
Output is correct |
63 |
Correct |
221 ms |
86020 KB |
Output is correct |
64 |
Correct |
219 ms |
86200 KB |
Output is correct |
65 |
Correct |
217 ms |
86188 KB |
Output is correct |
66 |
Correct |
240 ms |
86188 KB |
Output is correct |
67 |
Correct |
235 ms |
86188 KB |
Output is correct |
68 |
Correct |
214 ms |
80208 KB |
Output is correct |
69 |
Correct |
230 ms |
80148 KB |
Output is correct |
70 |
Correct |
225 ms |
80184 KB |
Output is correct |
71 |
Correct |
232 ms |
80052 KB |
Output is correct |
72 |
Correct |
225 ms |
80184 KB |
Output is correct |
73 |
Correct |
226 ms |
80208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
8 ms |
3928 KB |
Output is correct |
26 |
Correct |
8 ms |
3672 KB |
Output is correct |
27 |
Correct |
8 ms |
3756 KB |
Output is correct |
28 |
Correct |
8 ms |
3672 KB |
Output is correct |
29 |
Correct |
8 ms |
3672 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
255 ms |
167856 KB |
Output is correct |
32 |
Correct |
211 ms |
167800 KB |
Output is correct |
33 |
Correct |
240 ms |
166228 KB |
Output is correct |
34 |
Correct |
213 ms |
168368 KB |
Output is correct |
35 |
Correct |
122 ms |
160232 KB |
Output is correct |
36 |
Correct |
116 ms |
160428 KB |
Output is correct |
37 |
Correct |
185 ms |
159952 KB |
Output is correct |
38 |
Correct |
175 ms |
159956 KB |
Output is correct |
39 |
Correct |
182 ms |
160316 KB |
Output is correct |
40 |
Correct |
176 ms |
160356 KB |
Output is correct |
41 |
Correct |
182 ms |
163108 KB |
Output is correct |
42 |
Correct |
212 ms |
163344 KB |
Output is correct |
43 |
Correct |
183 ms |
163140 KB |
Output is correct |
44 |
Correct |
202 ms |
162752 KB |
Output is correct |
45 |
Correct |
207 ms |
169992 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Correct |
0 ms |
344 KB |
Output is correct |
48 |
Correct |
1 ms |
344 KB |
Output is correct |
49 |
Correct |
0 ms |
344 KB |
Output is correct |
50 |
Correct |
181 ms |
160220 KB |
Output is correct |
51 |
Correct |
184 ms |
160232 KB |
Output is correct |
52 |
Correct |
179 ms |
160292 KB |
Output is correct |
53 |
Correct |
188 ms |
160216 KB |
Output is correct |
54 |
Correct |
186 ms |
165836 KB |
Output is correct |
55 |
Correct |
213 ms |
165832 KB |
Output is correct |
56 |
Correct |
180 ms |
166028 KB |
Output is correct |
57 |
Correct |
185 ms |
165848 KB |
Output is correct |
58 |
Correct |
144 ms |
171856 KB |
Output is correct |
59 |
Correct |
154 ms |
172056 KB |
Output is correct |
60 |
Correct |
144 ms |
171976 KB |
Output is correct |
61 |
Correct |
145 ms |
172048 KB |
Output is correct |
62 |
Correct |
127 ms |
160036 KB |
Output is correct |
63 |
Correct |
112 ms |
160144 KB |
Output is correct |
64 |
Correct |
119 ms |
159952 KB |
Output is correct |
65 |
Correct |
114 ms |
159956 KB |
Output is correct |
66 |
Correct |
0 ms |
344 KB |
Output is correct |
67 |
Correct |
0 ms |
344 KB |
Output is correct |
68 |
Correct |
1 ms |
344 KB |
Output is correct |
69 |
Correct |
1 ms |
340 KB |
Output is correct |
70 |
Correct |
1 ms |
344 KB |
Output is correct |
71 |
Correct |
1 ms |
344 KB |
Output is correct |
72 |
Correct |
1 ms |
600 KB |
Output is correct |
73 |
Correct |
8 ms |
3928 KB |
Output is correct |
74 |
Correct |
139 ms |
171976 KB |
Output is correct |
75 |
Correct |
142 ms |
172004 KB |
Output is correct |
76 |
Correct |
140 ms |
171808 KB |
Output is correct |
77 |
Correct |
139 ms |
171980 KB |
Output is correct |
78 |
Correct |
226 ms |
86384 KB |
Output is correct |
79 |
Correct |
221 ms |
86188 KB |
Output is correct |
80 |
Correct |
245 ms |
86464 KB |
Output is correct |
81 |
Correct |
219 ms |
86188 KB |
Output is correct |
82 |
Correct |
224 ms |
86192 KB |
Output is correct |
83 |
Correct |
251 ms |
86076 KB |
Output is correct |
84 |
Correct |
447 ms |
171852 KB |
Output is correct |
85 |
Correct |
434 ms |
171872 KB |
Output is correct |
86 |
Correct |
506 ms |
172048 KB |
Output is correct |
87 |
Correct |
502 ms |
171856 KB |
Output is correct |
88 |
Correct |
486 ms |
171852 KB |
Output is correct |
89 |
Correct |
460 ms |
171856 KB |
Output is correct |
90 |
Correct |
0 ms |
344 KB |
Output is correct |
91 |
Correct |
1 ms |
344 KB |
Output is correct |
92 |
Correct |
1 ms |
344 KB |
Output is correct |
93 |
Correct |
1 ms |
344 KB |
Output is correct |
94 |
Correct |
1 ms |
344 KB |
Output is correct |
95 |
Correct |
1 ms |
600 KB |
Output is correct |
96 |
Correct |
7 ms |
3672 KB |
Output is correct |
97 |
Correct |
110 ms |
160336 KB |
Output is correct |
98 |
Correct |
112 ms |
159952 KB |
Output is correct |
99 |
Correct |
110 ms |
160144 KB |
Output is correct |
100 |
Correct |
121 ms |
160224 KB |
Output is correct |
101 |
Correct |
211 ms |
80192 KB |
Output is correct |
102 |
Correct |
269 ms |
80188 KB |
Output is correct |
103 |
Correct |
244 ms |
80132 KB |
Output is correct |
104 |
Correct |
246 ms |
80196 KB |
Output is correct |
105 |
Correct |
254 ms |
80204 KB |
Output is correct |
106 |
Correct |
237 ms |
80048 KB |
Output is correct |
107 |
Correct |
400 ms |
160148 KB |
Output is correct |
108 |
Correct |
486 ms |
160132 KB |
Output is correct |
109 |
Correct |
435 ms |
159964 KB |
Output is correct |
110 |
Correct |
495 ms |
159956 KB |
Output is correct |
111 |
Correct |
487 ms |
159976 KB |
Output is correct |
112 |
Correct |
499 ms |
160316 KB |
Output is correct |
113 |
Correct |
223 ms |
82888 KB |
Output is correct |
114 |
Correct |
220 ms |
83552 KB |
Output is correct |
115 |
Correct |
242 ms |
83836 KB |
Output is correct |
116 |
Correct |
234 ms |
84288 KB |
Output is correct |
117 |
Correct |
249 ms |
84380 KB |
Output is correct |
118 |
Correct |
253 ms |
83660 KB |
Output is correct |
119 |
Correct |
244 ms |
80064 KB |
Output is correct |
120 |
Correct |
239 ms |
80076 KB |
Output is correct |
121 |
Correct |
266 ms |
80244 KB |
Output is correct |
122 |
Correct |
272 ms |
80276 KB |
Output is correct |
123 |
Correct |
273 ms |
80188 KB |
Output is correct |
124 |
Correct |
225 ms |
80448 KB |
Output is correct |
125 |
Correct |
242 ms |
81852 KB |
Output is correct |
126 |
Correct |
234 ms |
81448 KB |
Output is correct |
127 |
Correct |
264 ms |
81512 KB |
Output is correct |
128 |
Correct |
223 ms |
81836 KB |
Output is correct |
129 |
Correct |
253 ms |
81420 KB |
Output is correct |
130 |
Correct |
294 ms |
82048 KB |
Output is correct |
131 |
Correct |
226 ms |
83816 KB |
Output is correct |
132 |
Correct |
254 ms |
84992 KB |
Output is correct |
133 |
Correct |
248 ms |
83524 KB |
Output is correct |
134 |
Correct |
229 ms |
80188 KB |
Output is correct |
135 |
Correct |
261 ms |
80176 KB |
Output is correct |
136 |
Correct |
255 ms |
80212 KB |
Output is correct |
137 |
Correct |
237 ms |
80208 KB |
Output is correct |
138 |
Correct |
263 ms |
80192 KB |
Output is correct |
139 |
Correct |
227 ms |
80208 KB |
Output is correct |
140 |
Correct |
223 ms |
83012 KB |
Output is correct |
141 |
Correct |
236 ms |
83172 KB |
Output is correct |
142 |
Correct |
245 ms |
83004 KB |
Output is correct |
143 |
Correct |
246 ms |
83184 KB |
Output is correct |
144 |
Correct |
237 ms |
82996 KB |
Output is correct |
145 |
Correct |
216 ms |
86184 KB |
Output is correct |
146 |
Correct |
221 ms |
86020 KB |
Output is correct |
147 |
Correct |
219 ms |
86200 KB |
Output is correct |
148 |
Correct |
217 ms |
86188 KB |
Output is correct |
149 |
Correct |
240 ms |
86188 KB |
Output is correct |
150 |
Correct |
235 ms |
86188 KB |
Output is correct |
151 |
Correct |
214 ms |
80208 KB |
Output is correct |
152 |
Correct |
230 ms |
80148 KB |
Output is correct |
153 |
Correct |
225 ms |
80184 KB |
Output is correct |
154 |
Correct |
232 ms |
80052 KB |
Output is correct |
155 |
Correct |
225 ms |
80184 KB |
Output is correct |
156 |
Correct |
226 ms |
80208 KB |
Output is correct |
157 |
Correct |
593 ms |
166916 KB |
Output is correct |
158 |
Correct |
532 ms |
167736 KB |
Output is correct |
159 |
Correct |
541 ms |
166856 KB |
Output is correct |
160 |
Correct |
582 ms |
166140 KB |
Output is correct |
161 |
Correct |
562 ms |
168212 KB |
Output is correct |
162 |
Correct |
587 ms |
168028 KB |
Output is correct |
163 |
Correct |
508 ms |
160152 KB |
Output is correct |
164 |
Correct |
467 ms |
160152 KB |
Output is correct |
165 |
Correct |
566 ms |
160208 KB |
Output is correct |
166 |
Correct |
595 ms |
160216 KB |
Output is correct |
167 |
Correct |
578 ms |
160224 KB |
Output is correct |
168 |
Correct |
499 ms |
160472 KB |
Output is correct |
169 |
Correct |
546 ms |
162964 KB |
Output is correct |
170 |
Correct |
554 ms |
162540 KB |
Output is correct |
171 |
Correct |
554 ms |
162780 KB |
Output is correct |
172 |
Correct |
505 ms |
162164 KB |
Output is correct |
173 |
Correct |
533 ms |
162892 KB |
Output is correct |
174 |
Correct |
517 ms |
163488 KB |
Output is correct |
175 |
Correct |
480 ms |
167336 KB |
Output is correct |
176 |
Correct |
483 ms |
169692 KB |
Output is correct |
177 |
Correct |
527 ms |
171368 KB |
Output is correct |
178 |
Correct |
486 ms |
160396 KB |
Output is correct |
179 |
Correct |
516 ms |
160216 KB |
Output is correct |
180 |
Correct |
507 ms |
160200 KB |
Output is correct |
181 |
Correct |
595 ms |
160464 KB |
Output is correct |
182 |
Correct |
571 ms |
160088 KB |
Output is correct |
183 |
Correct |
566 ms |
160468 KB |
Output is correct |
184 |
Correct |
466 ms |
166024 KB |
Output is correct |
185 |
Correct |
515 ms |
165832 KB |
Output is correct |
186 |
Correct |
513 ms |
165836 KB |
Output is correct |
187 |
Correct |
492 ms |
165676 KB |
Output is correct |
188 |
Correct |
541 ms |
166028 KB |
Output is correct |