oj.uz

Submission #526121

# Submission time Handle Problem Language Result Execution time Memory
526121 2022-02-13T19:15:30 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
21 / 25
 7000 ms 523620 KB 
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;

struct Item {
    int posde = (int)-1e9;
    int negde = (int)-1e9;
    int ans = (int)-1e9;
} tree_split[1048576];

Item f(const Item a, const Item b) {
    Item ret = { max(a.posde, b.posde), max(a.negde, b.negde), max(a.ans, b.ans) };
    ret.ans = max(ret.ans, a.posde + b.negde);
    return ret;
}

Item query_split(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return Item{ (int)-1e9, (int)-1e9, (int)-1e9 };
    if (l <= b && e <= r) return tree_split[i];
    int m = (b + e) / 2;
    return f(query_split(i * 2 + 1, b, m, l, r), query_split(i * 2 + 2, m + 1, e, l, r));
}

int n, m;
vector<int> tree[500006], child[500006];
vector<pair<int, int>> adj[500006];
int sz[500006], depth[500006];
int in[500006], top[500006], T;
int sp[19][500006], sp_dist[19][500006], sp_half[19][500006];
multiset<int> lt_depth[500006], lt_dist[500006];
int max_depth[500006], rev_max_depth[500006], dist[500006], rev_dist[500006];
int prev_dist[500006], prev_depth[500006][2];

int query_sp_half(int Ap, int x) {
    int ret = prev_depth[x][0] - depth[x];
    if (Ap == -1) return ret;
    for (int t = 18; t >= 0; t--) if (sp[t][x] != -1 && depth[sp[t][x]] >= depth[Ap]) {
        ret = max(ret, sp_half[t][x]);
        x = sp[t][x];
    }
    return max(ret, sp_half[0][x]);
}

int query_hld_res(int u, int v) {
    vector<Item> z;
    int pv = -1;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        if (pv != -1) lt_depth[u].erase(lt_depth[u].find(max_depth[pv] + 1));
        int V = (lt_depth[u].empty() ? 0 : *lt_depth[u].rbegin());
        z.push_back(Item{ V + depth[u], V - depth[u], (int)-1e9 });
        if (pv != -1) lt_depth[u].insert(max_depth[pv] + 1);
        z.push_back(query_split(0, 0, 524287, in[top[u]], in[u] - 1));
        if (z.back().posde == (int)-1e9) z.pop_back();
        pv = top[u];
        u = sp[0][top[u]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    if (pv != -1) lt_depth[u].erase(lt_depth[u].find(max_depth[pv] + 1));
    int V = (lt_depth[u].empty() ? 0 : *lt_depth[u].rbegin());
    z.push_back(Item{ V + depth[u], V - depth[u], (int)-1e9 });
    if (pv != -1) lt_depth[u].insert(max_depth[pv] + 1);
    z.push_back(query_split(0, 0, 524287, in[v], in[u] - 1));
    if (z.back().posde == (int)-1e9) z.pop_back();
    reverse(z.begin(), z.end());
    int ret = (int)-1e9;
    for (auto &i: z) ret = max(ret, i.ans);
    for (int i = 0; i < (int)z.size(); i++) for (int j = i + 1; j < (int)z.size(); j++) ret = max(ret, z[i].posde + z[j].negde);
    return ret;
}

int dfs_dist(int x) {
    vector<int> v;
    max_depth[x] = 0;
    dist[x] = 0;
    for (auto &i: child[x]) {
        v.push_back(dfs_dist(i) + 1);
        max_depth[x] = max(max_depth[x], v.back());
        dist[x] = max(dist[x], dist[i]);
    }
    int v0 = max_element(v.begin(), v.end()) - v.begin();
    int X = v[v0];
    if (!v.empty()) v[v0] = 0;
    int v1 = max_element(v.begin(), v.end()) - v.begin();
    v[v0] = X;
    if (!v.empty()) dist[x] = max(dist[x], v[v0]);
    if ((int)v.size() > 1) dist[x] = max(dist[x], v[v0] + v[v1]);
    return max_depth[x];
}

void dfs_rev_dist(int x) {
    multiset<int> v, u, w;
    v.insert(rev_max_depth[x]);
    u.insert(rev_dist[x]);
    for (auto &i: child[x]) {
        v.insert(max_depth[i] + 1);
        u.insert(dist[i]);
    }
    for (auto &i: child[x]) {
        v.erase(v.find(max_depth[i] + 1));
        u.erase(u.find(dist[i]));
        if (!u.empty()) rev_dist[i] = *u.rbegin();
        if (!v.empty()) rev_dist[i] = max(rev_dist[i], rev_max_depth[i] = *v.rbegin() + 1);
        if ((int)v.size() > 1) rev_dist[i] = max(rev_dist[i], *v.rbegin() + *prev(prev(v.end())));
        v.insert(max_depth[i] + 1);
        u.insert(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].erase(lt_dist[x].find(dist[i]));
        sp_dist[0][i] = (lt_dist[x].empty() ? 0 : *lt_dist[x].rbegin());
        lt_dist[x].insert(dist[i]);
    }
    for (auto &i: child[x]) dfs_f_dist(i);
}

void dfs_edge(int x) {
    for (auto &i: child[x]) {
        lt_depth[x].erase(lt_depth[x].find(max_depth[i] + 1));
        if ((int)lt_depth[x].size() > 1) sp_dist[0][i] = max(sp_dist[0][i], *lt_depth[x].rbegin() + *prev(prev(lt_depth[x].end())));
        else if (!lt_depth[x].empty()) sp_dist[0][i] = max(sp_dist[0][i], *lt_depth[x].rbegin());
        int V = (lt_depth[x].empty() ? 0 : *lt_depth[x].rbegin());
        sp_half[0][i] = V - depth[x];
        lt_depth[x].insert(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) {
        child[x].push_back(i);
        dfs_child(i, x);
    }
}

int dfs_sz(int x) {
    sz[x] = 1;
    for (auto &i: child[x]) {
        depth[i] = depth[x] + 1;
        sz[x] += dfs_sz(i);
        if (sz[i] > sz[child[x][0]]) swap(child[x][0], i);
    }
    return sz[x];
}

void dfs_hld(int x) {
    in[x] = T++;
    for (auto &i: child[x]) {
        top[i] = (i == child[x][0] ? top[x] : i);
        dfs_hld(i);
    }
}

int lca(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        ret += depth[u] - depth[sp[0][top[u]]];
        u = sp[0][top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    return u;
}

int pr(int x, int y) {
    for (int t = 18; t >= 0; t--) if (y >= 1 << t) {
        y -= 1 << t;
        x = sp[t][x];
    }
    return x;
}

int query_sp_dist(int u, int v, int l, int A, int B) {
    int ret = 0;
    if (u != l) {
        ret = max(prev_depth[u][1], prev_dist[u]);
        u = sp[0][u];
    }
    if (v != l) {
        ret = max(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].erase(lt_dist[l].find(dist[A]));
    if (B != -1) lt_dist[l].erase(lt_dist[l].find(dist[B]));
    ret = max(ret, lt_dist[l].empty() ? 0 : *lt_dist[l].rbegin());
    if (A != -1) lt_dist[l].insert(dist[A]);
    if (B != -1) lt_dist[l].insert(dist[B]);
    if (A != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[A] + 1));
    if (B != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[B] + 1));
    if (!lt_depth[l].empty()) ret = max(ret, *lt_depth[l].rbegin() + rev_max_depth[l]);
    else ret = max(ret, rev_max_depth[l]);
    if ((int)lt_depth[l].size() > 1) ret = max(ret, *lt_depth[l].rbegin() + *prev(prev(lt_depth[l].end())));
    if (A != -1) lt_depth[l].insert(max_depth[A] + 1);
    if (B != -1) lt_depth[l].insert(max_depth[B] + 1);
    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[x].push_back({ y, w });
            adj[y].push_back({ x, w });
        }
    }
    dfs_child(0);
    dfs_sz(0);
    dfs_hld(0);
    dfs_dist(0);
    dfs_rev_dist(0);
    for (int i = 0; i < n; i++) for (auto &j: child[i]) {
        lt_depth[i].insert(max_depth[j] + 1);
        lt_dist[i].insert(dist[j]);
    }
    for (int i = 0; i < n; i++) {
        prev_dist[i] = (lt_dist[i].empty() ? (int)-1e9 : *lt_dist[i].rbegin());
        prev_depth[i][0] = (lt_depth[i].empty() ? (int)-1e9 : *lt_depth[i].rbegin());
        prev_depth[i][1] = ((int)lt_depth[i].size() < 2 ? (int)-1e9 : *lt_depth[i].rbegin() + *prev(prev(lt_depth[i].end())));
    }
    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_half[t][i] = sp_half[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_half[t][i] = max(sp_half[t - 1][i], sp_half[t - 1][sp[t - 1][i]]);
        }
    }
    for (int i = 0; i < n; i++) {
        int v = 0;
        if (!child[i].empty()) lt_depth[i].erase(lt_depth[i].find(max_depth[child[i][0]] + 1));
        if (!lt_depth[i].empty()) v = *lt_depth[i].rbegin();
        if (!child[i].empty()) lt_depth[i].insert(max_depth[child[i][0]] + 1);
        tree_split[524287 + in[i]] = { v + depth[i], v - depth[i], (int)-1e9 };
    }
    for (int i = 524286; i >= 0; i--) tree_split[i] = f(tree_split[i * 2 + 1], tree_split[i * 2 + 2]);
    int zero = 2 * (n - 1) - dist[0], one = (int)1e9;
    for (int i = 0; i < n; i++) for (auto &j: adj[i]) if (i < j.first) {
        int l = lca(i, j.first);
        int ds = depth[i] + depth[j.first] - depth[l] - depth[l];
        int curr = j.second + 2 * (n - 1) - ds - 1;
        int A = (i == l ? -1 : pr(i, depth[i] - depth[l] - 1));
        int B = (j.first == l ? -1 : pr(j.first, depth[j.first] - depth[l] - 1));
        int y = max(rev_dist[l] - 1, query_sp_dist(i, j.first, l, A, B) - 1);
        int Ap = (depth[i] - depth[l] - 2 >= 0 ? pr(i, depth[i] - depth[l] - 2) : -1);
        int Bp = (depth[j.first] - depth[l] - 2 >= 0 ? pr(j.first, depth[j.first] - depth[l] - 2) : -1);
        if (A != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[A] + 1));
        if (B != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[B] + 1));
        int G = 0;
        if (!lt_depth[l].empty()) G = *lt_depth[l].rbegin();
        else y = max(y, rev_max_depth[l] - 1);
        if ((int)lt_depth[l].size() > 1) y = max(y, *lt_depth[l].rbegin() + *prev(prev(lt_depth[l].end())) - 1);
        if (A != -1) lt_depth[l].insert(max_depth[A] + 1);
        if (B != -1) lt_depth[l].insert(max_depth[B] + 1);
        int Alt = (A == -1 ? (int)-1e9 : query_sp_half(Ap, i) + depth[l]);
        int Brt = (B == -1 ? (int)-1e9 : query_sp_half(Bp, j.first) + depth[l]);
        int Lt = max(rev_max_depth[l], G);
        y = max(y, Alt + max(Brt, Lt) + 1);
        y = max(y, max(Alt, Lt) + Brt + 1);
        if (A != -1) y = max(y, query_hld_res(A, i) + 1);
        if (B != -1) y = max(y, query_hld_res(B, j.first) + 1);
        curr -= y;
        one = min(one, curr);
    }
    printf("%d", min(zero, one));
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct
16 Correct 43 ms 89148 KB Output is correct
17 Correct 47 ms 89156 KB Output is correct
18 Correct 45 ms 89060 KB Output is correct
19 Correct 45 ms 89052 KB Output is correct
20 Correct 45 ms 89160 KB Output is correct
21 Correct 44 ms 89156 KB Output is correct
22 Correct 44 ms 89156 KB Output is correct
23 Correct 44 ms 89100 KB Output is correct
24 Correct 44 ms 89164 KB Output is correct
25 Correct 45 ms 89152 KB Output is correct
26 Correct 47 ms 89156 KB Output is correct
27 Correct 44 ms 89164 KB Output is correct
28 Correct 44 ms 89164 KB Output is correct
29 Correct 50 ms 89040 KB Output is correct
30 Correct 45 ms 89116 KB Output is correct
31 Correct 44 ms 89164 KB Output is correct
32 Correct 44 ms 89080 KB Output is correct
33 Correct 44 ms 89028 KB Output is correct
34 Correct 46 ms 89100 KB Output is correct
35 Correct 44 ms 89144 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 92768 KB Output is correct
2 Correct 64 ms 93224 KB Output is correct
3 Correct 64 ms 92308 KB Output is correct
4 Correct 63 ms 92024 KB Output is correct
5 Correct 63 ms 91968 KB Output is correct
6 Correct 62 ms 91460 KB Output is correct
7 Correct 63 ms 92996 KB Output is correct
8 Correct 64 ms 92436 KB Output is correct
9 Correct 62 ms 92996 KB Output is correct
10 Correct 64 ms 91976 KB Output is correct
11 Correct 64 ms 92448 KB Output is correct
12 Correct 62 ms 91832 KB Output is correct
13 Correct 63 ms 92100 KB Output is correct
14 Correct 65 ms 92380 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct
16 Correct 43 ms 89148 KB Output is correct
17 Correct 47 ms 89156 KB Output is correct
18 Correct 45 ms 89060 KB Output is correct
19 Correct 45 ms 89052 KB Output is correct
20 Correct 45 ms 89160 KB Output is correct
21 Correct 44 ms 89156 KB Output is correct
22 Correct 44 ms 89156 KB Output is correct
23 Correct 44 ms 89100 KB Output is correct
24 Correct 44 ms 89164 KB Output is correct
25 Correct 45 ms 89152 KB Output is correct
26 Correct 47 ms 89156 KB Output is correct
27 Correct 44 ms 89164 KB Output is correct
28 Correct 44 ms 89164 KB Output is correct
29 Correct 50 ms 89040 KB Output is correct
30 Correct 45 ms 89116 KB Output is correct
31 Correct 44 ms 89164 KB Output is correct
32 Correct 44 ms 89080 KB Output is correct
33 Correct 44 ms 89028 KB Output is correct
34 Correct 46 ms 89100 KB Output is correct
35 Correct 44 ms 89144 KB Output is correct
36 Correct 44 ms 89156 KB Output is correct
37 Correct 44 ms 89208 KB Output is correct
38 Correct 44 ms 89108 KB Output is correct
39 Correct 47 ms 89160 KB Output is correct
40 Correct 43 ms 89140 KB Output is correct
41 Correct 45 ms 89152 KB Output is correct
42 Correct 45 ms 89120 KB Output is correct
43 Correct 45 ms 89204 KB Output is correct
44 Correct 44 ms 89132 KB Output is correct
45 Correct 46 ms 89156 KB Output is correct
46 Correct 47 ms 89188 KB Output is correct
47 Correct 46 ms 89180 KB Output is correct
48 Correct 44 ms 89096 KB Output is correct
49 Correct 44 ms 89196 KB Output is correct

Subtask #5
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct
16 Correct 43 ms 89148 KB Output is correct
17 Correct 47 ms 89156 KB Output is correct
18 Correct 45 ms 89060 KB Output is correct
19 Correct 45 ms 89052 KB Output is correct
20 Correct 45 ms 89160 KB Output is correct
21 Correct 44 ms 89156 KB Output is correct
22 Correct 44 ms 89156 KB Output is correct
23 Correct 44 ms 89100 KB Output is correct
24 Correct 44 ms 89164 KB Output is correct
25 Correct 45 ms 89152 KB Output is correct
26 Correct 47 ms 89156 KB Output is correct
27 Correct 44 ms 89164 KB Output is correct
28 Correct 44 ms 89164 KB Output is correct
29 Correct 50 ms 89040 KB Output is correct
30 Correct 45 ms 89116 KB Output is correct
31 Correct 44 ms 89164 KB Output is correct
32 Correct 44 ms 89080 KB Output is correct
33 Correct 44 ms 89028 KB Output is correct
34 Correct 46 ms 89100 KB Output is correct
35 Correct 44 ms 89144 KB Output is correct
36 Correct 44 ms 89156 KB Output is correct
37 Correct 44 ms 89208 KB Output is correct
38 Correct 44 ms 89108 KB Output is correct
39 Correct 47 ms 89160 KB Output is correct
40 Correct 43 ms 89140 KB Output is correct
41 Correct 45 ms 89152 KB Output is correct
42 Correct 45 ms 89120 KB Output is correct
43 Correct 45 ms 89204 KB Output is correct
44 Correct 44 ms 89132 KB Output is correct
45 Correct 46 ms 89156 KB Output is correct
46 Correct 47 ms 89188 KB Output is correct
47 Correct 46 ms 89180 KB Output is correct
48 Correct 44 ms 89096 KB Output is correct
49 Correct 44 ms 89196 KB Output is correct
50 Correct 48 ms 89440 KB Output is correct
51 Correct 45 ms 89432 KB Output is correct
52 Correct 45 ms 89412 KB Output is correct
53 Correct 45 ms 89412 KB Output is correct
54 Correct 45 ms 89336 KB Output is correct
55 Correct 46 ms 89324 KB Output is correct
56 Correct 48 ms 89408 KB Output is correct
57 Correct 46 ms 89412 KB Output is correct
58 Correct 47 ms 89496 KB Output is correct
59 Correct 45 ms 89412 KB Output is correct
60 Correct 45 ms 89364 KB Output is correct
61 Correct 45 ms 89332 KB Output is correct
62 Correct 46 ms 89396 KB Output is correct
63 Correct 45 ms 89420 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct
16 Correct 43 ms 89148 KB Output is correct
17 Correct 47 ms 89156 KB Output is correct
18 Correct 45 ms 89060 KB Output is correct
19 Correct 45 ms 89052 KB Output is correct
20 Correct 45 ms 89160 KB Output is correct
21 Correct 44 ms 89156 KB Output is correct
22 Correct 44 ms 89156 KB Output is correct
23 Correct 44 ms 89100 KB Output is correct
24 Correct 44 ms 89164 KB Output is correct
25 Correct 45 ms 89152 KB Output is correct
26 Correct 47 ms 89156 KB Output is correct
27 Correct 44 ms 89164 KB Output is correct
28 Correct 44 ms 89164 KB Output is correct
29 Correct 50 ms 89040 KB Output is correct
30 Correct 45 ms 89116 KB Output is correct
31 Correct 44 ms 89164 KB Output is correct
32 Correct 44 ms 89080 KB Output is correct
33 Correct 44 ms 89028 KB Output is correct
34 Correct 46 ms 89100 KB Output is correct
35 Correct 44 ms 89144 KB Output is correct
36 Correct 66 ms 92768 KB Output is correct
37 Correct 64 ms 93224 KB Output is correct
38 Correct 64 ms 92308 KB Output is correct
39 Correct 63 ms 92024 KB Output is correct
40 Correct 63 ms 91968 KB Output is correct
41 Correct 62 ms 91460 KB Output is correct
42 Correct 63 ms 92996 KB Output is correct
43 Correct 64 ms 92436 KB Output is correct
44 Correct 62 ms 92996 KB Output is correct
45 Correct 64 ms 91976 KB Output is correct
46 Correct 64 ms 92448 KB Output is correct
47 Correct 62 ms 91832 KB Output is correct
48 Correct 63 ms 92100 KB Output is correct
49 Correct 65 ms 92380 KB Output is correct
50 Correct 44 ms 89156 KB Output is correct
51 Correct 44 ms 89208 KB Output is correct
52 Correct 44 ms 89108 KB Output is correct
53 Correct 47 ms 89160 KB Output is correct
54 Correct 43 ms 89140 KB Output is correct
55 Correct 45 ms 89152 KB Output is correct
56 Correct 45 ms 89120 KB Output is correct
57 Correct 45 ms 89204 KB Output is correct
58 Correct 44 ms 89132 KB Output is correct
59 Correct 46 ms 89156 KB Output is correct
60 Correct 47 ms 89188 KB Output is correct
61 Correct 46 ms 89180 KB Output is correct
62 Correct 44 ms 89096 KB Output is correct
63 Correct 44 ms 89196 KB Output is correct
64 Correct 48 ms 89440 KB Output is correct
65 Correct 45 ms 89432 KB Output is correct
66 Correct 45 ms 89412 KB Output is correct
67 Correct 45 ms 89412 KB Output is correct
68 Correct 45 ms 89336 KB Output is correct
69 Correct 46 ms 89324 KB Output is correct
70 Correct 48 ms 89408 KB Output is correct
71 Correct 46 ms 89412 KB Output is correct
72 Correct 47 ms 89496 KB Output is correct
73 Correct 45 ms 89412 KB Output is correct
74 Correct 45 ms 89364 KB Output is correct
75 Correct 45 ms 89332 KB Output is correct
76 Correct 46 ms 89396 KB Output is correct
77 Correct 45 ms 89420 KB Output is correct
78 Correct 68 ms 92476 KB Output is correct
79 Correct 64 ms 92504 KB Output is correct
80 Correct 72 ms 92180 KB Output is correct
81 Correct 61 ms 92108 KB Output is correct
82 Correct 61 ms 91852 KB Output is correct
83 Correct 66 ms 91516 KB Output is correct
84 Correct 62 ms 92356 KB Output is correct
85 Correct 63 ms 92616 KB Output is correct
86 Correct 61 ms 92740 KB Output is correct
87 Correct 63 ms 92152 KB Output is correct
88 Correct 67 ms 92164 KB Output is correct
89 Correct 65 ms 91920 KB Output is correct
90 Correct 54 ms 91772 KB Output is correct
91 Correct 53 ms 91968 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct
16 Correct 43 ms 89148 KB Output is correct
17 Correct 47 ms 89156 KB Output is correct
18 Correct 45 ms 89060 KB Output is correct
19 Correct 45 ms 89052 KB Output is correct
20 Correct 45 ms 89160 KB Output is correct
21 Correct 44 ms 89156 KB Output is correct
22 Correct 44 ms 89156 KB Output is correct
23 Correct 44 ms 89100 KB Output is correct
24 Correct 44 ms 89164 KB Output is correct
25 Correct 45 ms 89152 KB Output is correct
26 Correct 47 ms 89156 KB Output is correct
27 Correct 44 ms 89164 KB Output is correct
28 Correct 44 ms 89164 KB Output is correct
29 Correct 50 ms 89040 KB Output is correct
30 Correct 45 ms 89116 KB Output is correct
31 Correct 44 ms 89164 KB Output is correct
32 Correct 44 ms 89080 KB Output is correct
33 Correct 44 ms 89028 KB Output is correct
34 Correct 46 ms 89100 KB Output is correct
35 Correct 44 ms 89144 KB Output is correct
36 Correct 66 ms 92768 KB Output is correct
37 Correct 64 ms 93224 KB Output is correct
38 Correct 64 ms 92308 KB Output is correct
39 Correct 63 ms 92024 KB Output is correct
40 Correct 63 ms 91968 KB Output is correct
41 Correct 62 ms 91460 KB Output is correct
42 Correct 63 ms 92996 KB Output is correct
43 Correct 64 ms 92436 KB Output is correct
44 Correct 62 ms 92996 KB Output is correct
45 Correct 64 ms 91976 KB Output is correct
46 Correct 64 ms 92448 KB Output is correct
47 Correct 62 ms 91832 KB Output is correct
48 Correct 63 ms 92100 KB Output is correct
49 Correct 65 ms 92380 KB Output is correct
50 Correct 44 ms 89156 KB Output is correct
51 Correct 44 ms 89208 KB Output is correct
52 Correct 44 ms 89108 KB Output is correct
53 Correct 47 ms 89160 KB Output is correct
54 Correct 43 ms 89140 KB Output is correct
55 Correct 45 ms 89152 KB Output is correct
56 Correct 45 ms 89120 KB Output is correct
57 Correct 45 ms 89204 KB Output is correct
58 Correct 44 ms 89132 KB Output is correct
59 Correct 46 ms 89156 KB Output is correct
60 Correct 47 ms 89188 KB Output is correct
61 Correct 46 ms 89180 KB Output is correct
62 Correct 44 ms 89096 KB Output is correct
63 Correct 44 ms 89196 KB Output is correct
64 Correct 48 ms 89440 KB Output is correct
65 Correct 45 ms 89432 KB Output is correct
66 Correct 45 ms 89412 KB Output is correct
67 Correct 45 ms 89412 KB Output is correct
68 Correct 45 ms 89336 KB Output is correct
69 Correct 46 ms 89324 KB Output is correct
70 Correct 48 ms 89408 KB Output is correct
71 Correct 46 ms 89412 KB Output is correct
72 Correct 47 ms 89496 KB Output is correct
73 Correct 45 ms 89412 KB Output is correct
74 Correct 45 ms 89364 KB Output is correct
75 Correct 45 ms 89332 KB Output is correct
76 Correct 46 ms 89396 KB Output is correct
77 Correct 45 ms 89420 KB Output is correct
78 Correct 68 ms 92476 KB Output is correct
79 Correct 64 ms 92504 KB Output is correct
80 Correct 72 ms 92180 KB Output is correct
81 Correct 61 ms 92108 KB Output is correct
82 Correct 61 ms 91852 KB Output is correct
83 Correct 66 ms 91516 KB Output is correct
84 Correct 62 ms 92356 KB Output is correct
85 Correct 63 ms 92616 KB Output is correct
86 Correct 61 ms 92740 KB Output is correct
87 Correct 63 ms 92152 KB Output is correct
88 Correct 67 ms 92164 KB Output is correct
89 Correct 65 ms 91920 KB Output is correct
90 Correct 54 ms 91772 KB Output is correct
91 Correct 53 ms 91968 KB Output is correct
92 Correct 539 ms 135920 KB Output is correct
93 Correct 557 ms 135736 KB Output is correct
94 Correct 411 ms 132460 KB Output is correct
95 Correct 251 ms 135664 KB Output is correct
96 Correct 246 ms 135372 KB Output is correct
97 Correct 547 ms 147572 KB Output is correct
98 Correct 549 ms 150480 KB Output is correct
99 Correct 547 ms 135132 KB Output is correct
100 Correct 604 ms 136512 KB Output is correct
101 Correct 543 ms 134756 KB Output is correct
102 Correct 489 ms 125504 KB Output is correct
103 Correct 527 ms 144956 KB Output is correct
104 Correct 620 ms 136820 KB Output is correct
105 Correct 557 ms 139404 KB Output is correct

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 89160 KB Output is correct
2 Correct 44 ms 89156 KB Output is correct
3 Correct 44 ms 89156 KB Output is correct
4 Correct 49 ms 89156 KB Output is correct
5 Correct 46 ms 89152 KB Output is correct
6 Correct 45 ms 89144 KB Output is correct
7 Correct 44 ms 89032 KB Output is correct
8 Correct 44 ms 89040 KB Output is correct
9 Correct 44 ms 89156 KB Output is correct
10 Correct 45 ms 89028 KB Output is correct
11 Correct 45 ms 89116 KB Output is correct
12 Correct 44 ms 89028 KB Output is correct
13 Correct 46 ms 89072 KB Output is correct
14 Correct 46 ms 89092 KB Output is correct
15 Correct 45 ms 89156 KB Output is correct
16 Correct 43 ms 89148 KB Output is correct
17 Correct 47 ms 89156 KB Output is correct
18 Correct 45 ms 89060 KB Output is correct
19 Correct 45 ms 89052 KB Output is correct
20 Correct 45 ms 89160 KB Output is correct
21 Correct 44 ms 89156 KB Output is correct
22 Correct 44 ms 89156 KB Output is correct
23 Correct 44 ms 89100 KB Output is correct
24 Correct 44 ms 89164 KB Output is correct
25 Correct 45 ms 89152 KB Output is correct
26 Correct 47 ms 89156 KB Output is correct
27 Correct 44 ms 89164 KB Output is correct
28 Correct 44 ms 89164 KB Output is correct
29 Correct 50 ms 89040 KB Output is correct
30 Correct 45 ms 89116 KB Output is correct
31 Correct 44 ms 89164 KB Output is correct
32 Correct 44 ms 89080 KB Output is correct
33 Correct 44 ms 89028 KB Output is correct
34 Correct 46 ms 89100 KB Output is correct
35 Correct 44 ms 89144 KB Output is correct
36 Correct 66 ms 92768 KB Output is correct
37 Correct 64 ms 93224 KB Output is correct
38 Correct 64 ms 92308 KB Output is correct
39 Correct 63 ms 92024 KB Output is correct
40 Correct 63 ms 91968 KB Output is correct
41 Correct 62 ms 91460 KB Output is correct
42 Correct 63 ms 92996 KB Output is correct
43 Correct 64 ms 92436 KB Output is correct
44 Correct 62 ms 92996 KB Output is correct
45 Correct 64 ms 91976 KB Output is correct
46 Correct 64 ms 92448 KB Output is correct
47 Correct 62 ms 91832 KB Output is correct
48 Correct 63 ms 92100 KB Output is correct
49 Correct 65 ms 92380 KB Output is correct
50 Correct 44 ms 89156 KB Output is correct
51 Correct 44 ms 89208 KB Output is correct
52 Correct 44 ms 89108 KB Output is correct
53 Correct 47 ms 89160 KB Output is correct
54 Correct 43 ms 89140 KB Output is correct
55 Correct 45 ms 89152 KB Output is correct
56 Correct 45 ms 89120 KB Output is correct
57 Correct 45 ms 89204 KB Output is correct
58 Correct 44 ms 89132 KB Output is correct
59 Correct 46 ms 89156 KB Output is correct
60 Correct 47 ms 89188 KB Output is correct
61 Correct 46 ms 89180 KB Output is correct
62 Correct 44 ms 89096 KB Output is correct
63 Correct 44 ms 89196 KB Output is correct
64 Correct 48 ms 89440 KB Output is correct
65 Correct 45 ms 89432 KB Output is correct
66 Correct 45 ms 89412 KB Output is correct
67 Correct 45 ms 89412 KB Output is correct
68 Correct 45 ms 89336 KB Output is correct
69 Correct 46 ms 89324 KB Output is correct
70 Correct 48 ms 89408 KB Output is correct
71 Correct 46 ms 89412 KB Output is correct
72 Correct 47 ms 89496 KB Output is correct
73 Correct 45 ms 89412 KB Output is correct
74 Correct 45 ms 89364 KB Output is correct
75 Correct 45 ms 89332 KB Output is correct
76 Correct 46 ms 89396 KB Output is correct
77 Correct 45 ms 89420 KB Output is correct
78 Correct 68 ms 92476 KB Output is correct
79 Correct 64 ms 92504 KB Output is correct
80 Correct 72 ms 92180 KB Output is correct
81 Correct 61 ms 92108 KB Output is correct
82 Correct 61 ms 91852 KB Output is correct
83 Correct 66 ms 91516 KB Output is correct
84 Correct 62 ms 92356 KB Output is correct
85 Correct 63 ms 92616 KB Output is correct
86 Correct 61 ms 92740 KB Output is correct
87 Correct 63 ms 92152 KB Output is correct
88 Correct 67 ms 92164 KB Output is correct
89 Correct 65 ms 91920 KB Output is correct
90 Correct 54 ms 91772 KB Output is correct
91 Correct 53 ms 91968 KB Output is correct
92 Correct 539 ms 135920 KB Output is correct
93 Correct 557 ms 135736 KB Output is correct
94 Correct 411 ms 132460 KB Output is correct
95 Correct 251 ms 135664 KB Output is correct
96 Correct 246 ms 135372 KB Output is correct
97 Correct 547 ms 147572 KB Output is correct
98 Correct 549 ms 150480 KB Output is correct
99 Correct 547 ms 135132 KB Output is correct
100 Correct 604 ms 136512 KB Output is correct
101 Correct 543 ms 134756 KB Output is correct
102 Correct 489 ms 125504 KB Output is correct
103 Correct 527 ms 144956 KB Output is correct
104 Correct 620 ms 136820 KB Output is correct
105 Correct 557 ms 139404 KB Output is correct
106 Execution timed out 7040 ms 523620 KB Time limit exceeded
107 Halted 0 ms 0 KB -