oj.uz

Submission #978233

# Submission time Handle Problem Language Result Execution time Memory
978233 2024-05-09T04:16:08 Z model_code JOI tour (JOI24_joitour) C++17
100 / 100
 607 ms 97908 KB 
// static toptree 解 O((N + Q) log N)
#include "joitour.h"
#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;

/*
    頂点 0 を根とする根付き木で考える．
    上の boundary vertex を u, 下の boundary vertex を v とする．
    頂点属性を辺属性に変換するため，頂点の情報を，その頂点から上に伸びる辺に載せる．(ダミーの頂点を頂点 0 の上に作る)
    したがって，各 cluster は F[u] が分からないものとして情報を集めることになる．
    各 cluster が持つ情報:
    f_v  : F[v]
    c_012: cluster 内の 0 - 1 - 2 パスの個数
    c_01u: cluster 内の 0 - 1 - u パスの個数
    c_u12: cluster 内の u - 1 - 2 パスの個数
    c_0u2: cluster 内の 0 - u - 2 パスの個数
    c_01v: cluster 内の 0 - 1 - v パス (v が 1 を担当しても良い) の個数
    c_v12: cluster 内の v - 1 - 2 パス (v が 1 を担当しても良い) の個数
    c_0uv: cluster 内の 0 - u - v パスの個数
    c_u1v: cluster 内の u - 1 - v パス (v が 1 を担当しても良い) の個数
    c_vu2: cluster 内の v - u - 2 パスの個数
    c_0  : cluster 内の 0 の個数
    c_2  : cluster 内の 2 の個数
*/
struct T {
    long long f_v, c_012, c_01u, c_u12, c_0u2, c_01v, c_v12, c_0uv, c_u1v, c_vu2, c_0, c_2;
};
T one(int f) {
    T x = {};
    x.f_v = f;
    if (f == 0) x.c_0++;
    if (f == 1) x.c_u1v++;
    if (f == 2) x.c_2++;
    return x;
}
T rake(const T& a, const T& b) {
    // a.u == b.u である 2 つの cluster をマージ
    return T{
        a.f_v,
        a.c_012 + b.c_012 + a.c_01u * b.c_2 + a.c_0 * b.c_u12 + b.c_0 * a.c_u12 + b.c_01u * a.c_2,
        a.c_01u + b.c_01u,
        a.c_u12 + b.c_u12,
        a.c_0u2 + b.c_0u2 + a.c_0 * b.c_2 + b.c_0 * a.c_2,
        a.c_01v + b.c_01u + b.c_0 * a.c_u1v,
        a.c_v12 + b.c_u12 + a.c_u1v * b.c_2,
        a.c_0uv + b.c_0,
        a.c_u1v,
        a.c_vu2 + b.c_2,
        a.c_0 + b.c_0,
        a.c_2 + b.c_2};
}
T compress(const T& a, const T& b) {
    // a.v == b.u である 2 つの cluster をマージ
    return T{
        b.f_v,
        a.c_012 + b.c_012 + a.c_01v * b.c_2 + a.c_0 * b.c_u12 + b.c_0 * a.c_v12 + b.c_01u * a.c_2 + b.c_0u2 * (a.f_v == 1),
        a.c_01u + b.c_01u + b.c_0 * a.c_u1v,
        a.c_u12 + b.c_u12 + a.c_u1v * b.c_2,
        a.c_0u2 + a.c_0uv * b.c_2 + b.c_0 * a.c_vu2,
        a.c_01v + b.c_01v + a.c_0 * b.c_u1v + b.c_0uv * (a.f_v == 1),
        a.c_v12 + b.c_v12 + b.c_u1v * a.c_2 + (a.f_v == 1) * b.c_vu2,
        a.c_0uv,
        a.c_u1v + b.c_u1v,
        a.c_vu2,
        a.c_0 + b.c_0,
        a.c_2 + b.c_2};
}

vector<T> D;
vector<int> P, L, R, T;

void update(int i) {
    D[i] = (T[i] ? compress : rake)(D[L[i]], D[R[i]]);
}

void init(int N, vector<int> F, vector<int> U, vector<int> V, int Q) {
    vector g(N, vector<int>{});
    for (int i = 0; i < N - 1; i++) {
        int u = U[i], v = V[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // static toptree の構築
    P.resize(N);
    L.resize(N);
    R.resize(N);
    T.resize(N);
    for (int f : F) D.push_back(one(f));

    vector<int> sz(N, 1);  // 部分木の大きさ
    {
        // heavy path の構築
        auto dfs = [&](auto dfs, int i) -> void {
            for (int j : g[i]) {
                // erase(g[j], i);
                g[j].erase(find(begin(g[j]), end(g[j]), i));
                dfs(dfs, j);
                sz[i] += sz[j];
            }
            if (size(g[i])) {
                // iter_swap(ranges::max_element(g[i], {}, [&](int i) { return sz[i]; }), begin(g[i]));
                auto it = max_element(begin(g[i]), end(g[i]), [&](int i, int j) { return sz[i] < sz[j]; });
                iter_swap(it, begin(g[i]));
            }
        };
        dfs(dfs, 0);
    }

    // data[i] と data[j] を rake/compress して新しいノードを作る
    auto op_D = [&](int i, int j, int t) -> int {
        const int K = size(D);
        T.push_back(t);
        L.push_back(i);
        R.push_back(j);
        P.push_back(0);
        D.emplace_back();
        P[i] = K;
        P[j] = K;
        return K;
    };

    auto merge_dfs = [&](auto merge_dfs, const vector<pair<int, int>>& a, int t) -> pair<int, int> {
        // 頂点数の合計が半分になるように分割して再帰的に rake/compress
        if (size(a) == 1) return a[0];
        int sum_s = 0;
        for (auto [i, s] : a) sum_s += s;
        vector<pair<int, int>> b, c;
        for (auto [i, s] : a) {
            (sum_s > s ? b : c).emplace_back(i, s);
            sum_s -= s * 2;
        }
        auto [i, si] = merge_dfs(merge_dfs, b, t);
        auto [j, sj] = merge_dfs(merge_dfs, c, t);
        return {op_D(i, j, t), si + sj};
    };

    auto collect_r = [&](auto collect_r, auto collect_c, int i) -> pair<int, int> {
        // 頂点 i から下に出るすべての辺を heavy 方向へ rake
        vector<pair<int, int>> childs;
        childs.emplace_back(g[i][0], 1);
        for (int j = 1; j < size(g[i]); j++) childs.push_back(collect_c(collect_r, collect_c, g[i][j]));
        return merge_dfs(merge_dfs, childs, 0);
    };

    auto collect_c = [&](auto collect_r, auto collect_c, int i) -> pair<int, int> {
        // par[i] -> i 辺とその先の heavy path を compress
        vector<pair<int, int>> path = {{i, 1}};
        while (size(g[i])) {
            path.push_back(collect_r(collect_r, collect_c, i));
            i = g[i][0];
        }
        return merge_dfs(merge_dfs, path, 1);
    };
    collect_c(collect_r, collect_c, 0);
    assert(size(D) == N * 2 - 1);

    // 木に沿って計算
    for (int i = N; i < size(D); i++) update(i);
}

void change(int X, int Y) {
    D[X] = one(Y);
    while (P[X]) update(X = P[X]);
}

long long num_tours() {
    return D.back().c_012;
}

Compilation message

joitour.cpp: In instantiation of 'init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)::<lambda(auto:3, auto:4, int)> [with auto:3 = init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)::<lambda(auto:3, auto:4, int)>; auto:4 = init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)::<lambda(auto:5, auto:6, int)>]':
joitour.cpp:152:37:   required from 'init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)::<lambda(auto:5, auto:6, int)> [with auto:5 = init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)::<lambda(auto:3, auto:4, int)>; auto:6 = init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)::<lambda(auto:5, auto:6, int)>]'
joitour.cpp:157:39:   required from here
joitour.cpp:144:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for (int j = 1; j < size(g[i]); j++) childs.push_back(collect_c(collect_r, collect_c, g[i][j]));
      |                         ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from joitour.cpp:4:
joitour.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, int)':
joitour.cpp:158:20: warning: comparison of integer expressions of different signedness: 'std::vector<T>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  158 |     assert(size(D) == N * 2 - 1);
      |            ~~~~~~~~^~~~~~~~~~~~
joitour.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<T>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = N; i < size(D); i++) update(i);
      |                     ~~^~~~~~~~~

Subtask #1
6.0 / 6.0

# 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 828 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 500 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 648 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 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 356 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 856 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

Subtask #2
8.0 / 8.0

# 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 828 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 500 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 648 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 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 356 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 856 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 7 ms 1876 KB Output is correct
26 Correct 7 ms 1876 KB Output is correct
27 Correct 7 ms 1744 KB Output is correct
28 Correct 6 ms 2392 KB Output is correct
29 Correct 7 ms 1876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 220 ms 85704 KB Output is correct
3 Correct 243 ms 85232 KB Output is correct
4 Correct 230 ms 81096 KB Output is correct
5 Correct 233 ms 86612 KB Output is correct
6 Correct 124 ms 70228 KB Output is correct
7 Correct 137 ms 70272 KB Output is correct
8 Correct 184 ms 70076 KB Output is correct
9 Correct 215 ms 70292 KB Output is correct
10 Correct 188 ms 70376 KB Output is correct
11 Correct 180 ms 71072 KB Output is correct
12 Correct 189 ms 77268 KB Output is correct
13 Correct 202 ms 77260 KB Output is correct
14 Correct 229 ms 77024 KB Output is correct
15 Correct 190 ms 76428 KB Output is correct
16 Correct 242 ms 91860 KB Output is correct
17 Correct 0 ms 352 KB Output is correct
18 Correct 0 ms 356 KB Output is correct
19 Correct 0 ms 352 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 194 ms 70352 KB Output is correct
22 Correct 188 ms 70360 KB Output is correct
23 Correct 177 ms 70332 KB Output is correct
24 Correct 220 ms 70224 KB Output is correct
25 Correct 152 ms 76032 KB Output is correct
26 Correct 153 ms 76240 KB Output is correct
27 Correct 178 ms 76180 KB Output is correct
28 Correct 183 ms 76244 KB Output is correct
29 Correct 144 ms 97224 KB Output is correct
30 Correct 143 ms 97232 KB Output is correct
31 Correct 143 ms 97420 KB Output is correct
32 Correct 153 ms 97220 KB Output is correct
33 Correct 133 ms 70084 KB Output is correct
34 Correct 118 ms 70196 KB Output is correct
35 Correct 120 ms 70236 KB Output is correct
36 Correct 120 ms 70284 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 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 344 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 8 ms 2144 KB Output is correct
9 Correct 148 ms 97236 KB Output is correct
10 Correct 152 ms 97164 KB Output is correct
11 Correct 152 ms 97220 KB Output is correct
12 Correct 159 ms 97236 KB Output is correct
13 Correct 214 ms 48840 KB Output is correct
14 Correct 198 ms 48776 KB Output is correct
15 Correct 233 ms 48908 KB Output is correct
16 Correct 215 ms 48776 KB Output is correct
17 Correct 231 ms 48948 KB Output is correct
18 Correct 240 ms 48788 KB Output is correct
19 Correct 456 ms 97676 KB Output is correct
20 Correct 415 ms 97248 KB Output is correct
21 Correct 457 ms 97704 KB Output is correct
22 Correct 491 ms 97476 KB Output is correct
23 Correct 502 ms 97408 KB Output is correct
24 Correct 478 ms 97484 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 596 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 604 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 122 ms 70124 KB Output is correct
9 Correct 130 ms 70128 KB Output is correct
10 Correct 119 ms 70140 KB Output is correct
11 Correct 120 ms 70228 KB Output is correct
12 Correct 197 ms 35296 KB Output is correct
13 Correct 252 ms 35200 KB Output is correct
14 Correct 213 ms 35484 KB Output is correct
15 Correct 209 ms 35324 KB Output is correct
16 Correct 211 ms 35208 KB Output is correct
17 Correct 203 ms 35388 KB Output is correct
18 Correct 426 ms 70440 KB Output is correct
19 Correct 498 ms 70368 KB Output is correct
20 Correct 536 ms 70136 KB Output is correct
21 Correct 450 ms 70120 KB Output is correct
22 Correct 466 ms 70088 KB Output is correct
23 Correct 456 ms 70320 KB Output is correct

Subtask #6
34.0 / 34.0

# 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 828 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 500 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 648 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 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 356 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 856 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 7 ms 1876 KB Output is correct
26 Correct 7 ms 1876 KB Output is correct
27 Correct 7 ms 1744 KB Output is correct
28 Correct 6 ms 2392 KB Output is correct
29 Correct 7 ms 1876 KB Output is correct
30 Correct 237 ms 39936 KB Output is correct
31 Correct 222 ms 42100 KB Output is correct
32 Correct 244 ms 42260 KB Output is correct
33 Correct 276 ms 43260 KB Output is correct
34 Correct 230 ms 43740 KB Output is correct
35 Correct 238 ms 41608 KB Output is correct
36 Correct 242 ms 35212 KB Output is correct
37 Correct 220 ms 35204 KB Output is correct
38 Correct 233 ms 35324 KB Output is correct
39 Correct 245 ms 35204 KB Output is correct
40 Correct 250 ms 35392 KB Output is correct
41 Correct 237 ms 35732 KB Output is correct
42 Correct 214 ms 38528 KB Output is correct
43 Correct 264 ms 37492 KB Output is correct
44 Correct 244 ms 38016 KB Output is correct
45 Correct 240 ms 38540 KB Output is correct
46 Correct 230 ms 37652 KB Output is correct
47 Correct 214 ms 39048 KB Output is correct
48 Correct 247 ms 42876 KB Output is correct
49 Correct 222 ms 45956 KB Output is correct
50 Correct 247 ms 42428 KB Output is correct
51 Correct 215 ms 35448 KB Output is correct
52 Correct 252 ms 35472 KB Output is correct
53 Correct 234 ms 35356 KB Output is correct
54 Correct 228 ms 35436 KB Output is correct
55 Correct 244 ms 35448 KB Output is correct
56 Correct 238 ms 35440 KB Output is correct
57 Correct 205 ms 38400 KB Output is correct
58 Correct 243 ms 38332 KB Output is correct
59 Correct 225 ms 38416 KB Output is correct
60 Correct 219 ms 38380 KB Output is correct
61 Correct 244 ms 38420 KB Output is correct
62 Correct 208 ms 48776 KB Output is correct
63 Correct 207 ms 49136 KB Output is correct
64 Correct 238 ms 48948 KB Output is correct
65 Correct 213 ms 48908 KB Output is correct
66 Correct 241 ms 48892 KB Output is correct
67 Correct 242 ms 48844 KB Output is correct
68 Correct 202 ms 35220 KB Output is correct
69 Correct 233 ms 35280 KB Output is correct
70 Correct 249 ms 35344 KB Output is correct
71 Correct 226 ms 35216 KB Output is correct
72 Correct 220 ms 35532 KB Output is correct
73 Correct 218 ms 35224 KB Output is correct

Subtask #7
14.0 / 14.0

# 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 828 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 500 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 648 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 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 356 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 856 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 7 ms 1876 KB Output is correct
26 Correct 7 ms 1876 KB Output is correct
27 Correct 7 ms 1744 KB Output is correct
28 Correct 6 ms 2392 KB Output is correct
29 Correct 7 ms 1876 KB Output is correct
30 Correct 0 ms 352 KB Output is correct
31 Correct 220 ms 85704 KB Output is correct
32 Correct 243 ms 85232 KB Output is correct
33 Correct 230 ms 81096 KB Output is correct
34 Correct 233 ms 86612 KB Output is correct
35 Correct 124 ms 70228 KB Output is correct
36 Correct 137 ms 70272 KB Output is correct
37 Correct 184 ms 70076 KB Output is correct
38 Correct 215 ms 70292 KB Output is correct
39 Correct 188 ms 70376 KB Output is correct
40 Correct 180 ms 71072 KB Output is correct
41 Correct 189 ms 77268 KB Output is correct
42 Correct 202 ms 77260 KB Output is correct
43 Correct 229 ms 77024 KB Output is correct
44 Correct 190 ms 76428 KB Output is correct
45 Correct 242 ms 91860 KB Output is correct
46 Correct 0 ms 352 KB Output is correct
47 Correct 0 ms 356 KB Output is correct
48 Correct 0 ms 352 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 194 ms 70352 KB Output is correct
51 Correct 188 ms 70360 KB Output is correct
52 Correct 177 ms 70332 KB Output is correct
53 Correct 220 ms 70224 KB Output is correct
54 Correct 152 ms 76032 KB Output is correct
55 Correct 153 ms 76240 KB Output is correct
56 Correct 178 ms 76180 KB Output is correct
57 Correct 183 ms 76244 KB Output is correct
58 Correct 144 ms 97224 KB Output is correct
59 Correct 143 ms 97232 KB Output is correct
60 Correct 143 ms 97420 KB Output is correct
61 Correct 153 ms 97220 KB Output is correct
62 Correct 133 ms 70084 KB Output is correct
63 Correct 118 ms 70196 KB Output is correct
64 Correct 120 ms 70236 KB Output is correct
65 Correct 120 ms 70284 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 0 ms 600 KB Output is correct
68 Correct 1 ms 344 KB Output is correct
69 Correct 1 ms 344 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 856 KB Output is correct
73 Correct 8 ms 2144 KB Output is correct
74 Correct 148 ms 97236 KB Output is correct
75 Correct 152 ms 97164 KB Output is correct
76 Correct 152 ms 97220 KB Output is correct
77 Correct 159 ms 97236 KB Output is correct
78 Correct 214 ms 48840 KB Output is correct
79 Correct 198 ms 48776 KB Output is correct
80 Correct 233 ms 48908 KB Output is correct
81 Correct 215 ms 48776 KB Output is correct
82 Correct 231 ms 48948 KB Output is correct
83 Correct 240 ms 48788 KB Output is correct
84 Correct 456 ms 97676 KB Output is correct
85 Correct 415 ms 97248 KB Output is correct
86 Correct 457 ms 97704 KB Output is correct
87 Correct 491 ms 97476 KB Output is correct
88 Correct 502 ms 97408 KB Output is correct
89 Correct 478 ms 97484 KB Output is correct
90 Correct 0 ms 344 KB Output is correct
91 Correct 1 ms 596 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 604 KB Output is correct
96 Correct 8 ms 1708 KB Output is correct
97 Correct 122 ms 70124 KB Output is correct
98 Correct 130 ms 70128 KB Output is correct
99 Correct 119 ms 70140 KB Output is correct
100 Correct 120 ms 70228 KB Output is correct
101 Correct 197 ms 35296 KB Output is correct
102 Correct 252 ms 35200 KB Output is correct
103 Correct 213 ms 35484 KB Output is correct
104 Correct 209 ms 35324 KB Output is correct
105 Correct 211 ms 35208 KB Output is correct
106 Correct 203 ms 35388 KB Output is correct
107 Correct 426 ms 70440 KB Output is correct
108 Correct 498 ms 70368 KB Output is correct
109 Correct 536 ms 70136 KB Output is correct
110 Correct 450 ms 70120 KB Output is correct
111 Correct 466 ms 70088 KB Output is correct
112 Correct 456 ms 70320 KB Output is correct
113 Correct 237 ms 39936 KB Output is correct
114 Correct 222 ms 42100 KB Output is correct
115 Correct 244 ms 42260 KB Output is correct
116 Correct 276 ms 43260 KB Output is correct
117 Correct 230 ms 43740 KB Output is correct
118 Correct 238 ms 41608 KB Output is correct
119 Correct 242 ms 35212 KB Output is correct
120 Correct 220 ms 35204 KB Output is correct
121 Correct 233 ms 35324 KB Output is correct
122 Correct 245 ms 35204 KB Output is correct
123 Correct 250 ms 35392 KB Output is correct
124 Correct 237 ms 35732 KB Output is correct
125 Correct 214 ms 38528 KB Output is correct
126 Correct 264 ms 37492 KB Output is correct
127 Correct 244 ms 38016 KB Output is correct
128 Correct 240 ms 38540 KB Output is correct
129 Correct 230 ms 37652 KB Output is correct
130 Correct 214 ms 39048 KB Output is correct
131 Correct 247 ms 42876 KB Output is correct
132 Correct 222 ms 45956 KB Output is correct
133 Correct 247 ms 42428 KB Output is correct
134 Correct 215 ms 35448 KB Output is correct
135 Correct 252 ms 35472 KB Output is correct
136 Correct 234 ms 35356 KB Output is correct
137 Correct 228 ms 35436 KB Output is correct
138 Correct 244 ms 35448 KB Output is correct
139 Correct 238 ms 35440 KB Output is correct
140 Correct 205 ms 38400 KB Output is correct
141 Correct 243 ms 38332 KB Output is correct
142 Correct 225 ms 38416 KB Output is correct
143 Correct 219 ms 38380 KB Output is correct
144 Correct 244 ms 38420 KB Output is correct
145 Correct 208 ms 48776 KB Output is correct
146 Correct 207 ms 49136 KB Output is correct
147 Correct 238 ms 48948 KB Output is correct
148 Correct 213 ms 48908 KB Output is correct
149 Correct 241 ms 48892 KB Output is correct
150 Correct 242 ms 48844 KB Output is correct
151 Correct 202 ms 35220 KB Output is correct
152 Correct 233 ms 35280 KB Output is correct
153 Correct 249 ms 35344 KB Output is correct
154 Correct 226 ms 35216 KB Output is correct
155 Correct 220 ms 35532 KB Output is correct
156 Correct 218 ms 35224 KB Output is correct
157 Correct 514 ms 83664 KB Output is correct
158 Correct 514 ms 85448 KB Output is correct
159 Correct 542 ms 82956 KB Output is correct
160 Correct 579 ms 81428 KB Output is correct
161 Correct 552 ms 86348 KB Output is correct
162 Correct 598 ms 86048 KB Output is correct
163 Correct 505 ms 70080 KB Output is correct
164 Correct 520 ms 70040 KB Output is correct
165 Correct 568 ms 70236 KB Output is correct
166 Correct 568 ms 70212 KB Output is correct
167 Correct 586 ms 70280 KB Output is correct
168 Correct 575 ms 71184 KB Output is correct
169 Correct 516 ms 76624 KB Output is correct
170 Correct 540 ms 75540 KB Output is correct
171 Correct 528 ms 75700 KB Output is correct
172 Correct 558 ms 74864 KB Output is correct
173 Correct 549 ms 76252 KB Output is correct
174 Correct 548 ms 77308 KB Output is correct
175 Correct 551 ms 85008 KB Output is correct
176 Correct 607 ms 90836 KB Output is correct
177 Correct 606 ms 97908 KB Output is correct
178 Correct 521 ms 70256 KB Output is correct
179 Correct 581 ms 70428 KB Output is correct
180 Correct 566 ms 70456 KB Output is correct
181 Correct 528 ms 70264 KB Output is correct
182 Correct 603 ms 70304 KB Output is correct
183 Correct 558 ms 70628 KB Output is correct
184 Correct 440 ms 76136 KB Output is correct
185 Correct 485 ms 76176 KB Output is correct
186 Correct 484 ms 76172 KB Output is correct
187 Correct 516 ms 76296 KB Output is correct
188 Correct 506 ms 76528 KB Output is correct