oj.uz

Submission #526160

# Submission time Handle Problem Language Result Execution time Memory
526160 2022-02-13T21:07:10 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
21 / 25
 7000 ms 391468 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <tuple>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;

struct Item {
    int posde;
    int negde;
    int ans;
    Item (): posde((int)-1e9), negde((int)-1e9), ans((int)-1e9) {}
    Item (int posde, int negde, int ans): posde(posde), negde(negde), ans(ans) {}
} sp_split[19][500006];

struct MySet {
    vector<int> v;
    MySet () {
        v.resize(3);
    }
    void push(int x) {
        v.push_back(x);
        int p = min_element(v.begin(), v.end()) - v.begin();
        swap(v[p], v.back());
        v.pop_back();
    }
    void pop(int x) {
        for (auto &i: v) if (i == x) {
            i = 0;
            return;
        }
    }
    int first() {
        return *max_element(v.begin(), v.end());
    }
    int second() {
        return v[0] + v[1] + v[2] - *min_element(v.begin(), v.end());
    }
} lt_depth[500006], lt_dist[500006];

int n, m;
vector<int> tree[500006], child[500006];
vector<tuple<int, int, int>> adj;
int depth[500006], sp[19][500006], sp_dist[19][500006];
int max_depth[500006], rev_max_depth[500006], dist[500006], rev_dist[500006];
int prev_dist[500006], prev_depth[500006][2];

inline Item query_sp_res(int A, int x) {
    if (A == -1) return Item();
    Item ret = { prev_depth[x][0] + depth[x], prev_depth[x][0] - depth[x], (int)-1e9 };
    if (A == x) return ret;
    for (int t = 18; t >= 0; t--) if (sp[t][x] != -1 && depth[sp[t][x]] > depth[A]) {
        ret.ans = max({ sp_split[t][x].ans, ret.ans, sp_split[t][x].posde + ret.negde });
        ret.posde = max(sp_split[t][x].posde, ret.posde);
        ret.negde = max(sp_split[t][x].negde, ret.negde);
        x = sp[t][x];
    }
    ret.ans = max({ sp_split[0][x].ans, ret.ans, sp_split[0][x].posde + ret.negde });
    ret.posde = max(sp_split[0][x].posde, ret.posde);
    ret.negde = max(sp_split[0][x].negde, ret.negde);
    return ret;
}

int dfs_dist(int x) {
    max_depth[x] = 0;
    dist[x] = 0;
    int mx0 = (int)-1e9, mx1 = (int)-1e9;
    for (auto &i: child[x]) {
        int t = dfs_dist(i) + 1;
        max_depth[x] = max(max_depth[x], t);
        if (t > mx0) mx1 = mx0, mx0 = t;
        else if (t > mx1) mx1 = t;
        dist[x] = max(dist[x], dist[i]);
    }
    dist[x] = max(dist[x], mx0 + max(mx1, 0));
    return max_depth[x];
}

void dfs_rev_dist(int x) {
    for (auto &i: child[x]) {
        lt_depth[x].push(max_depth[i] + 1);
        if (prev_depth[x][0] < max_depth[i] + 1) prev_depth[x][1] = prev_depth[x][0], prev_depth[x][0] = max_depth[i] + 1;
        else if (prev_depth[x][1] < max_depth[i] + 1) prev_depth[x][1] = max_depth[i] + 1;
        lt_dist[x].push(dist[i]);
        if (prev_dist[x] < dist[i]) prev_dist[x] = dist[i];
    }
    for (auto &i: child[x]) {
        lt_depth[x].pop(max_depth[i] + 1);
        lt_dist[x].pop(dist[i]);
        rev_dist[i] = max({ rev_max_depth[i] = max(lt_depth[x].first(), rev_max_depth[x]) + 1, lt_depth[x].second(), lt_depth[x].first() + rev_dist[x]});
        lt_depth[x].push(max_depth[i] + 1);
        lt_dist[x].push(dist[i]);
    }
    for (auto &i: child[x]) dfs_rev_dist(i);
}


void dfs_f_dist(int x) {
    for (auto &i: child[x]) {
        lt_dist[x].pop(dist[i]);
        sp_dist[0][i] = lt_dist[x].first();
        lt_dist[x].push(dist[i]);
    }
    for (auto &i: child[x]) dfs_f_dist(i);
}

void dfs_edge(int x) {
    for (auto &i: child[x]) {
        lt_depth[x].pop(max_depth[i] + 1);
        int V = lt_depth[x].first();
        sp_dist[0][i] = max(sp_dist[0][i], lt_depth[x].second());
        sp_split[0][i].posde = V + depth[x];
        sp_split[0][i].negde = V - depth[x];
        lt_depth[x].push(max_depth[i] + 1);
    }
    for (auto &i: child[x]) dfs_edge(i);
}

void dfs_child(int x, int prev = -1) {
    sp[0][x] = prev;
    for (auto &i: tree[x]) if (i != prev) {
        depth[i] = depth[x] + 1;
        child[x].push_back(i);
        dfs_child(i, x);
    }
}

int A, B;

inline int lca(int u, int v) {
    bool sw = false;
    if (depth[u] < depth[v]) swap(u, v), sw = true;
    int diff = depth[u] - depth[v] - 1;
    if (~diff) {
        for (int t = 18; t >= 0; t--) if (diff >= 1 << t) {
            diff -= 1 << t;
            u = sp[t][u];
        }
        if (sw) B = u;
        else A = u;
        u = sp[0][u];
        if (u == v) return u;
    }
    for (int t = 18; t >= 0; t--) if (sp[t][u] != -1 && sp[t][v] != -1 && sp[t][u] != sp[t][v]) {
        u = sp[t][u];
        v = sp[t][v];
    }
    A = u, B = v;
    if (sw) swap(A, B);
    return sp[0][u];
}

inline int query_sp_dist(int u, int v, int l, int A, int B, int G, int H) {
    int ret = 0;
    if (u != l) {
        ret = max(prev_depth[u][0] + prev_depth[u][1], prev_dist[u]);
        u = sp[0][u];
    }
    if (v != l) {
        ret = max(prev_depth[v][0] + prev_depth[v][1], prev_dist[v]);
        v = sp[0][v];
    }
    for (int t = 18; t >= 0; t--) if (sp[t][u] != -1 && depth[sp[t][u]] > depth[l]) {
        ret = max(ret, sp_dist[t][u]);
        u = sp[t][u];
    }
    for (int t = 18; t >= 0; t--) if (sp[t][v] != -1 && depth[sp[t][v]] > depth[l]) {
        ret = max(ret, sp_dist[t][v]);
        v = sp[t][v];
    }
    if (A != -1) lt_dist[l].pop(dist[A]);
    if (B != -1) lt_dist[l].pop(dist[B]);
    ret = max(ret, lt_dist[l].first());
    if (A != -1) lt_dist[l].push(dist[A]);
    if (B != -1) lt_dist[l].push(dist[B]);
    return ret;
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        if (w == 1) {
            tree[x].push_back(y);
            tree[y].push_back(x);
        } else adj.push_back({ x, y, w });
    }
    for (int i = 0; i < n; i++) prev_dist[i] = prev_depth[i][0] = prev_depth[i][1] = (int)-1e9;
    dfs_child(0);
    dfs_dist(0);
    dfs_rev_dist(0);
    dfs_f_dist(0);
    dfs_edge(0);
    for (int t = 1; t < 19; t++) for (int i = 0; i < n; i++) {
        if (sp[t - 1][i] == -1) {
            sp[t][i] = -1;
            sp_dist[t][i] = sp_dist[t - 1][i];
            sp_split[t][i] = sp_split[t - 1][i];
        } else {
            sp[t][i] = sp[t - 1][sp[t - 1][i]];
            sp_dist[t][i] = max(sp_dist[t - 1][i], sp_dist[t - 1][sp[t - 1][i]]);
            sp_split[t][i].ans = max({ sp_split[t - 1][sp[t - 1][i]].ans, sp_split[t - 1][i].ans, sp_split[t - 1][sp[t - 1][i]].posde + sp_split[t - 1][i].negde });
            sp_split[t][i].posde = max(sp_split[t - 1][sp[t - 1][i]].posde, sp_split[t - 1][i].posde);
            sp_split[t][i].negde = max(sp_split[t - 1][sp[t - 1][i]].negde, sp_split[t - 1][i].negde);
        }
    }
    int res = 2 * (n - 1) - dist[0];
    for (auto [ i, j, w ]: adj) {
        A = B = -1;
        int l = lca(i, j);
        int ds = depth[i] + depth[j] - depth[l] - depth[l];
        int curr = w + 2 * (n - 1) - ds - 1;
        int G = 0, H = 0, y = 0;
        if (A != -1) lt_depth[l].pop(max_depth[A] + 1);
        if (B != -1) lt_depth[l].pop(max_depth[B] + 1);
        G = lt_depth[l].first();
        y = max(y, G + rev_max_depth[l] - 1);
        y = max(y, lt_depth[l].second() - 1);
        if (A != -1) lt_depth[l].push(max_depth[A] + 1);
        if (B != -1) lt_depth[l].push(max_depth[B] + 1);
        Item first = query_sp_res(A, i);
        Item second = query_sp_res(B, j);
        int Alt = first.negde + depth[l];
        int Brt = second.negde + depth[l];
        int Lt = max(rev_max_depth[l], G);
        res = min(res, curr - max({ y, Alt + max(Brt, Lt) + 1, max(Alt, Lt) + Brt + 1, first.ans + 1, second.ans + 1, rev_dist[l] - 1, query_sp_dist(i, j, l, A, B, G, H) - 1 }));
    }
    printf("%d", res);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:185:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         scanf("%d%d%d", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct
16 Correct 119 ms 190340 KB Output is correct
17 Correct 119 ms 190420 KB Output is correct
18 Correct 121 ms 190396 KB Output is correct
19 Correct 117 ms 190384 KB Output is correct
20 Correct 124 ms 190412 KB Output is correct
21 Correct 119 ms 190452 KB Output is correct
22 Correct 120 ms 190412 KB Output is correct
23 Correct 131 ms 190448 KB Output is correct
24 Correct 124 ms 190508 KB Output is correct
25 Correct 121 ms 190404 KB Output is correct
26 Correct 119 ms 190404 KB Output is correct
27 Correct 121 ms 190424 KB Output is correct
28 Correct 119 ms 190348 KB Output is correct
29 Correct 123 ms 190404 KB Output is correct
30 Correct 120 ms 190412 KB Output is correct
31 Correct 120 ms 190452 KB Output is correct
32 Correct 120 ms 190444 KB Output is correct
33 Correct 121 ms 190324 KB Output is correct
34 Correct 121 ms 190456 KB Output is correct
35 Correct 119 ms 190376 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 192132 KB Output is correct
2 Correct 129 ms 192228 KB Output is correct
3 Correct 126 ms 192036 KB Output is correct
4 Correct 137 ms 191908 KB Output is correct
5 Correct 125 ms 191896 KB Output is correct
6 Correct 124 ms 191556 KB Output is correct
7 Correct 131 ms 192152 KB Output is correct
8 Correct 129 ms 191940 KB Output is correct
9 Correct 129 ms 192176 KB Output is correct
10 Correct 128 ms 191908 KB Output is correct
11 Correct 128 ms 192092 KB Output is correct
12 Correct 126 ms 191836 KB Output is correct
13 Correct 134 ms 191992 KB Output is correct
14 Correct 131 ms 191996 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct
16 Correct 119 ms 190340 KB Output is correct
17 Correct 119 ms 190420 KB Output is correct
18 Correct 121 ms 190396 KB Output is correct
19 Correct 117 ms 190384 KB Output is correct
20 Correct 124 ms 190412 KB Output is correct
21 Correct 119 ms 190452 KB Output is correct
22 Correct 120 ms 190412 KB Output is correct
23 Correct 131 ms 190448 KB Output is correct
24 Correct 124 ms 190508 KB Output is correct
25 Correct 121 ms 190404 KB Output is correct
26 Correct 119 ms 190404 KB Output is correct
27 Correct 121 ms 190424 KB Output is correct
28 Correct 119 ms 190348 KB Output is correct
29 Correct 123 ms 190404 KB Output is correct
30 Correct 120 ms 190412 KB Output is correct
31 Correct 120 ms 190452 KB Output is correct
32 Correct 120 ms 190444 KB Output is correct
33 Correct 121 ms 190324 KB Output is correct
34 Correct 121 ms 190456 KB Output is correct
35 Correct 119 ms 190376 KB Output is correct
36 Correct 123 ms 190472 KB Output is correct
37 Correct 121 ms 190396 KB Output is correct
38 Correct 121 ms 190404 KB Output is correct
39 Correct 119 ms 190356 KB Output is correct
40 Correct 128 ms 190472 KB Output is correct
41 Correct 124 ms 190476 KB Output is correct
42 Correct 118 ms 190580 KB Output is correct
43 Correct 121 ms 190472 KB Output is correct
44 Correct 121 ms 190352 KB Output is correct
45 Correct 121 ms 190412 KB Output is correct
46 Correct 123 ms 190492 KB Output is correct
47 Correct 119 ms 190372 KB Output is correct
48 Correct 119 ms 190404 KB Output is correct
49 Correct 130 ms 190376 KB Output is correct

Subtask #5
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct
16 Correct 119 ms 190340 KB Output is correct
17 Correct 119 ms 190420 KB Output is correct
18 Correct 121 ms 190396 KB Output is correct
19 Correct 117 ms 190384 KB Output is correct
20 Correct 124 ms 190412 KB Output is correct
21 Correct 119 ms 190452 KB Output is correct
22 Correct 120 ms 190412 KB Output is correct
23 Correct 131 ms 190448 KB Output is correct
24 Correct 124 ms 190508 KB Output is correct
25 Correct 121 ms 190404 KB Output is correct
26 Correct 119 ms 190404 KB Output is correct
27 Correct 121 ms 190424 KB Output is correct
28 Correct 119 ms 190348 KB Output is correct
29 Correct 123 ms 190404 KB Output is correct
30 Correct 120 ms 190412 KB Output is correct
31 Correct 120 ms 190452 KB Output is correct
32 Correct 120 ms 190444 KB Output is correct
33 Correct 121 ms 190324 KB Output is correct
34 Correct 121 ms 190456 KB Output is correct
35 Correct 119 ms 190376 KB Output is correct
36 Correct 123 ms 190472 KB Output is correct
37 Correct 121 ms 190396 KB Output is correct
38 Correct 121 ms 190404 KB Output is correct
39 Correct 119 ms 190356 KB Output is correct
40 Correct 128 ms 190472 KB Output is correct
41 Correct 124 ms 190476 KB Output is correct
42 Correct 118 ms 190580 KB Output is correct
43 Correct 121 ms 190472 KB Output is correct
44 Correct 121 ms 190352 KB Output is correct
45 Correct 121 ms 190412 KB Output is correct
46 Correct 123 ms 190492 KB Output is correct
47 Correct 119 ms 190372 KB Output is correct
48 Correct 119 ms 190404 KB Output is correct
49 Correct 130 ms 190376 KB Output is correct
50 Correct 130 ms 190584 KB Output is correct
51 Correct 119 ms 190532 KB Output is correct
52 Correct 121 ms 190536 KB Output is correct
53 Correct 121 ms 190592 KB Output is correct
54 Correct 125 ms 190596 KB Output is correct
55 Correct 122 ms 190468 KB Output is correct
56 Correct 122 ms 190532 KB Output is correct
57 Correct 122 ms 190560 KB Output is correct
58 Correct 119 ms 190612 KB Output is correct
59 Correct 123 ms 190600 KB Output is correct
60 Correct 119 ms 190536 KB Output is correct
61 Correct 121 ms 190492 KB Output is correct
62 Correct 125 ms 190480 KB Output is correct
63 Correct 128 ms 190660 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct
16 Correct 119 ms 190340 KB Output is correct
17 Correct 119 ms 190420 KB Output is correct
18 Correct 121 ms 190396 KB Output is correct
19 Correct 117 ms 190384 KB Output is correct
20 Correct 124 ms 190412 KB Output is correct
21 Correct 119 ms 190452 KB Output is correct
22 Correct 120 ms 190412 KB Output is correct
23 Correct 131 ms 190448 KB Output is correct
24 Correct 124 ms 190508 KB Output is correct
25 Correct 121 ms 190404 KB Output is correct
26 Correct 119 ms 190404 KB Output is correct
27 Correct 121 ms 190424 KB Output is correct
28 Correct 119 ms 190348 KB Output is correct
29 Correct 123 ms 190404 KB Output is correct
30 Correct 120 ms 190412 KB Output is correct
31 Correct 120 ms 190452 KB Output is correct
32 Correct 120 ms 190444 KB Output is correct
33 Correct 121 ms 190324 KB Output is correct
34 Correct 121 ms 190456 KB Output is correct
35 Correct 119 ms 190376 KB Output is correct
36 Correct 132 ms 192132 KB Output is correct
37 Correct 129 ms 192228 KB Output is correct
38 Correct 126 ms 192036 KB Output is correct
39 Correct 137 ms 191908 KB Output is correct
40 Correct 125 ms 191896 KB Output is correct
41 Correct 124 ms 191556 KB Output is correct
42 Correct 131 ms 192152 KB Output is correct
43 Correct 129 ms 191940 KB Output is correct
44 Correct 129 ms 192176 KB Output is correct
45 Correct 128 ms 191908 KB Output is correct
46 Correct 128 ms 192092 KB Output is correct
47 Correct 126 ms 191836 KB Output is correct
48 Correct 134 ms 191992 KB Output is correct
49 Correct 131 ms 191996 KB Output is correct
50 Correct 123 ms 190472 KB Output is correct
51 Correct 121 ms 190396 KB Output is correct
52 Correct 121 ms 190404 KB Output is correct
53 Correct 119 ms 190356 KB Output is correct
54 Correct 128 ms 190472 KB Output is correct
55 Correct 124 ms 190476 KB Output is correct
56 Correct 118 ms 190580 KB Output is correct
57 Correct 121 ms 190472 KB Output is correct
58 Correct 121 ms 190352 KB Output is correct
59 Correct 121 ms 190412 KB Output is correct
60 Correct 123 ms 190492 KB Output is correct
61 Correct 119 ms 190372 KB Output is correct
62 Correct 119 ms 190404 KB Output is correct
63 Correct 130 ms 190376 KB Output is correct
64 Correct 130 ms 190584 KB Output is correct
65 Correct 119 ms 190532 KB Output is correct
66 Correct 121 ms 190536 KB Output is correct
67 Correct 121 ms 190592 KB Output is correct
68 Correct 125 ms 190596 KB Output is correct
69 Correct 122 ms 190468 KB Output is correct
70 Correct 122 ms 190532 KB Output is correct
71 Correct 122 ms 190560 KB Output is correct
72 Correct 119 ms 190612 KB Output is correct
73 Correct 123 ms 190600 KB Output is correct
74 Correct 119 ms 190536 KB Output is correct
75 Correct 121 ms 190492 KB Output is correct
76 Correct 125 ms 190480 KB Output is correct
77 Correct 128 ms 190660 KB Output is correct
78 Correct 131 ms 192096 KB Output is correct
79 Correct 131 ms 192128 KB Output is correct
80 Correct 131 ms 192076 KB Output is correct
81 Correct 134 ms 192048 KB Output is correct
82 Correct 129 ms 191992 KB Output is correct
83 Correct 122 ms 191684 KB Output is correct
84 Correct 126 ms 192204 KB Output is correct
85 Correct 130 ms 192196 KB Output is correct
86 Correct 128 ms 192296 KB Output is correct
87 Correct 126 ms 192068 KB Output is correct
88 Correct 129 ms 192076 KB Output is correct
89 Correct 125 ms 191976 KB Output is correct
90 Correct 124 ms 191940 KB Output is correct
91 Correct 126 ms 192020 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct
16 Correct 119 ms 190340 KB Output is correct
17 Correct 119 ms 190420 KB Output is correct
18 Correct 121 ms 190396 KB Output is correct
19 Correct 117 ms 190384 KB Output is correct
20 Correct 124 ms 190412 KB Output is correct
21 Correct 119 ms 190452 KB Output is correct
22 Correct 120 ms 190412 KB Output is correct
23 Correct 131 ms 190448 KB Output is correct
24 Correct 124 ms 190508 KB Output is correct
25 Correct 121 ms 190404 KB Output is correct
26 Correct 119 ms 190404 KB Output is correct
27 Correct 121 ms 190424 KB Output is correct
28 Correct 119 ms 190348 KB Output is correct
29 Correct 123 ms 190404 KB Output is correct
30 Correct 120 ms 190412 KB Output is correct
31 Correct 120 ms 190452 KB Output is correct
32 Correct 120 ms 190444 KB Output is correct
33 Correct 121 ms 190324 KB Output is correct
34 Correct 121 ms 190456 KB Output is correct
35 Correct 119 ms 190376 KB Output is correct
36 Correct 132 ms 192132 KB Output is correct
37 Correct 129 ms 192228 KB Output is correct
38 Correct 126 ms 192036 KB Output is correct
39 Correct 137 ms 191908 KB Output is correct
40 Correct 125 ms 191896 KB Output is correct
41 Correct 124 ms 191556 KB Output is correct
42 Correct 131 ms 192152 KB Output is correct
43 Correct 129 ms 191940 KB Output is correct
44 Correct 129 ms 192176 KB Output is correct
45 Correct 128 ms 191908 KB Output is correct
46 Correct 128 ms 192092 KB Output is correct
47 Correct 126 ms 191836 KB Output is correct
48 Correct 134 ms 191992 KB Output is correct
49 Correct 131 ms 191996 KB Output is correct
50 Correct 123 ms 190472 KB Output is correct
51 Correct 121 ms 190396 KB Output is correct
52 Correct 121 ms 190404 KB Output is correct
53 Correct 119 ms 190356 KB Output is correct
54 Correct 128 ms 190472 KB Output is correct
55 Correct 124 ms 190476 KB Output is correct
56 Correct 118 ms 190580 KB Output is correct
57 Correct 121 ms 190472 KB Output is correct
58 Correct 121 ms 190352 KB Output is correct
59 Correct 121 ms 190412 KB Output is correct
60 Correct 123 ms 190492 KB Output is correct
61 Correct 119 ms 190372 KB Output is correct
62 Correct 119 ms 190404 KB Output is correct
63 Correct 130 ms 190376 KB Output is correct
64 Correct 130 ms 190584 KB Output is correct
65 Correct 119 ms 190532 KB Output is correct
66 Correct 121 ms 190536 KB Output is correct
67 Correct 121 ms 190592 KB Output is correct
68 Correct 125 ms 190596 KB Output is correct
69 Correct 122 ms 190468 KB Output is correct
70 Correct 122 ms 190532 KB Output is correct
71 Correct 122 ms 190560 KB Output is correct
72 Correct 119 ms 190612 KB Output is correct
73 Correct 123 ms 190600 KB Output is correct
74 Correct 119 ms 190536 KB Output is correct
75 Correct 121 ms 190492 KB Output is correct
76 Correct 125 ms 190480 KB Output is correct
77 Correct 128 ms 190660 KB Output is correct
78 Correct 131 ms 192096 KB Output is correct
79 Correct 131 ms 192128 KB Output is correct
80 Correct 131 ms 192076 KB Output is correct
81 Correct 134 ms 192048 KB Output is correct
82 Correct 129 ms 191992 KB Output is correct
83 Correct 122 ms 191684 KB Output is correct
84 Correct 126 ms 192204 KB Output is correct
85 Correct 130 ms 192196 KB Output is correct
86 Correct 128 ms 192296 KB Output is correct
87 Correct 126 ms 192068 KB Output is correct
88 Correct 129 ms 192076 KB Output is correct
89 Correct 125 ms 191976 KB Output is correct
90 Correct 124 ms 191940 KB Output is correct
91 Correct 126 ms 192020 KB Output is correct
92 Correct 455 ms 215448 KB Output is correct
93 Correct 449 ms 215312 KB Output is correct
94 Correct 369 ms 214108 KB Output is correct
95 Correct 250 ms 215100 KB Output is correct
96 Correct 270 ms 215080 KB Output is correct
97 Correct 431 ms 218800 KB Output is correct
98 Correct 442 ms 219872 KB Output is correct
99 Correct 449 ms 215168 KB Output is correct
100 Correct 434 ms 215768 KB Output is correct
101 Correct 447 ms 214988 KB Output is correct
102 Correct 204 ms 209788 KB Output is correct
103 Correct 423 ms 218220 KB Output is correct
104 Correct 436 ms 215052 KB Output is correct
105 Correct 435 ms 216272 KB Output is correct

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 190404 KB Output is correct
2 Correct 120 ms 190408 KB Output is correct
3 Correct 117 ms 190548 KB Output is correct
4 Correct 116 ms 190336 KB Output is correct
5 Correct 127 ms 190368 KB Output is correct
6 Correct 123 ms 190420 KB Output is correct
7 Correct 118 ms 190404 KB Output is correct
8 Correct 119 ms 190328 KB Output is correct
9 Correct 119 ms 190416 KB Output is correct
10 Correct 119 ms 190444 KB Output is correct
11 Correct 121 ms 190380 KB Output is correct
12 Correct 120 ms 190440 KB Output is correct
13 Correct 118 ms 190416 KB Output is correct
14 Correct 122 ms 190404 KB Output is correct
15 Correct 118 ms 190452 KB Output is correct
16 Correct 119 ms 190340 KB Output is correct
17 Correct 119 ms 190420 KB Output is correct
18 Correct 121 ms 190396 KB Output is correct
19 Correct 117 ms 190384 KB Output is correct
20 Correct 124 ms 190412 KB Output is correct
21 Correct 119 ms 190452 KB Output is correct
22 Correct 120 ms 190412 KB Output is correct
23 Correct 131 ms 190448 KB Output is correct
24 Correct 124 ms 190508 KB Output is correct
25 Correct 121 ms 190404 KB Output is correct
26 Correct 119 ms 190404 KB Output is correct
27 Correct 121 ms 190424 KB Output is correct
28 Correct 119 ms 190348 KB Output is correct
29 Correct 123 ms 190404 KB Output is correct
30 Correct 120 ms 190412 KB Output is correct
31 Correct 120 ms 190452 KB Output is correct
32 Correct 120 ms 190444 KB Output is correct
33 Correct 121 ms 190324 KB Output is correct
34 Correct 121 ms 190456 KB Output is correct
35 Correct 119 ms 190376 KB Output is correct
36 Correct 132 ms 192132 KB Output is correct
37 Correct 129 ms 192228 KB Output is correct
38 Correct 126 ms 192036 KB Output is correct
39 Correct 137 ms 191908 KB Output is correct
40 Correct 125 ms 191896 KB Output is correct
41 Correct 124 ms 191556 KB Output is correct
42 Correct 131 ms 192152 KB Output is correct
43 Correct 129 ms 191940 KB Output is correct
44 Correct 129 ms 192176 KB Output is correct
45 Correct 128 ms 191908 KB Output is correct
46 Correct 128 ms 192092 KB Output is correct
47 Correct 126 ms 191836 KB Output is correct
48 Correct 134 ms 191992 KB Output is correct
49 Correct 131 ms 191996 KB Output is correct
50 Correct 123 ms 190472 KB Output is correct
51 Correct 121 ms 190396 KB Output is correct
52 Correct 121 ms 190404 KB Output is correct
53 Correct 119 ms 190356 KB Output is correct
54 Correct 128 ms 190472 KB Output is correct
55 Correct 124 ms 190476 KB Output is correct
56 Correct 118 ms 190580 KB Output is correct
57 Correct 121 ms 190472 KB Output is correct
58 Correct 121 ms 190352 KB Output is correct
59 Correct 121 ms 190412 KB Output is correct
60 Correct 123 ms 190492 KB Output is correct
61 Correct 119 ms 190372 KB Output is correct
62 Correct 119 ms 190404 KB Output is correct
63 Correct 130 ms 190376 KB Output is correct
64 Correct 130 ms 190584 KB Output is correct
65 Correct 119 ms 190532 KB Output is correct
66 Correct 121 ms 190536 KB Output is correct
67 Correct 121 ms 190592 KB Output is correct
68 Correct 125 ms 190596 KB Output is correct
69 Correct 122 ms 190468 KB Output is correct
70 Correct 122 ms 190532 KB Output is correct
71 Correct 122 ms 190560 KB Output is correct
72 Correct 119 ms 190612 KB Output is correct
73 Correct 123 ms 190600 KB Output is correct
74 Correct 119 ms 190536 KB Output is correct
75 Correct 121 ms 190492 KB Output is correct
76 Correct 125 ms 190480 KB Output is correct
77 Correct 128 ms 190660 KB Output is correct
78 Correct 131 ms 192096 KB Output is correct
79 Correct 131 ms 192128 KB Output is correct
80 Correct 131 ms 192076 KB Output is correct
81 Correct 134 ms 192048 KB Output is correct
82 Correct 129 ms 191992 KB Output is correct
83 Correct 122 ms 191684 KB Output is correct
84 Correct 126 ms 192204 KB Output is correct
85 Correct 130 ms 192196 KB Output is correct
86 Correct 128 ms 192296 KB Output is correct
87 Correct 126 ms 192068 KB Output is correct
88 Correct 129 ms 192076 KB Output is correct
89 Correct 125 ms 191976 KB Output is correct
90 Correct 124 ms 191940 KB Output is correct
91 Correct 126 ms 192020 KB Output is correct
92 Correct 455 ms 215448 KB Output is correct
93 Correct 449 ms 215312 KB Output is correct
94 Correct 369 ms 214108 KB Output is correct
95 Correct 250 ms 215100 KB Output is correct
96 Correct 270 ms 215080 KB Output is correct
97 Correct 431 ms 218800 KB Output is correct
98 Correct 442 ms 219872 KB Output is correct
99 Correct 449 ms 215168 KB Output is correct
100 Correct 434 ms 215768 KB Output is correct
101 Correct 447 ms 214988 KB Output is correct
102 Correct 204 ms 209788 KB Output is correct
103 Correct 423 ms 218220 KB Output is correct
104 Correct 436 ms 215052 KB Output is correct
105 Correct 435 ms 216272 KB Output is correct
106 Execution timed out 7056 ms 391468 KB Time limit exceeded
107 Halted 0 ms 0 KB -