oj.uz

Submission #525862

# Submission time Handle Problem Language Result Execution time Memory
525862 2022-02-13T04:08:05 Z mjhmjh1104 Mountains and Valleys (CCO20_day1problem3) C++17
16 / 25
 7000 ms 58112 KB 
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;
 
int n, m;
vector<int> tree[200006], child[200006];
vector<pair<int, int>> adj[200006];
int _par[200006], _sz[200006];
int sz[200006], depth[200006], par[200006];
int in[200006], top[100006], T;
int sp[18][200006];
multiset<int> lt_depth[200006];
int max_depth[200006], rev_max_depth[200006], dist[200006], rev_dist[200006];
int edge[200006];
 
int dfs(int x, int prev = -1) {
    _par[x] = prev;
    _sz[x] = 1;
    for (auto &i: tree[x]) if (i != prev) {
        _sz[x] = max(_sz[x], dfs(i, x) + 1);
    }
    return _sz[x];
}
 
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;
    if (par[x] != -1) {
        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_edge(int x) {
    multiset<int> v;
    for (auto &i: child[x]) v.insert(max_depth[i] + 1);
    for (auto &i: child[x]) {
        v.erase(v.find(max_depth[i] + 1));
        if ((int)v.size() > 1) edge[i] = *v.rbegin() + *prev(prev(v.end()));
        else if (!v.empty()) edge[i] = *v.rbegin();
        v.insert(max_depth[i] + 1);
    }
    for (auto &i: child[x]) dfs_edge(i);
}

void dfs_child(int x, int prev = -1) {
    par[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[par[top[u]]];
        u = par[top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    return u;
}

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

int tree_dist[524288], tree_edge[524288];

int query_dist(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return 0;
    if (l <= b && e <= r) return tree_dist[i];
    int m = (b + e) / 2;
    return max(query_dist(i * 2 + 1, b, m, l, r), query_dist(i * 2 + 2, m + 1, e, l, r));
}

int query_edge(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return 0;
    if (l <= b && e <= r) return tree_edge[i];
    int m = (b + e) / 2;
    return max(query_edge(i * 2 + 1, b, m, l, r), query_edge(i * 2 + 2, m + 1, e, l, r));
}

vector<pair<int, int>> lt;

void query_hld(int u, int v) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        lt.push_back({ in[top[u]], in[u] });
        u = par[top[u]];
    }
    lt.push_back({ min(in[u], in[v]), max(in[u], in[v]) });
}

int query_hld_dist(int u, int v, int x, int y) {
    lt.clear();
    query_hld(u, v);
    sort(lt.begin(), lt.end());
    int ret = max(query_dist(0, 0, 262143, x, lt[0].first - 1), query_dist(0, 0, 262143, lt.back().second + 1, y));
    for (int i = 1; i < (int)lt.size(); i++) ret = max(ret, query_dist(0, 0, 262143, lt[i - 1].second + 1, lt[i].first - 1));
    return ret;
}

int query_hld_edge(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        ret = max(ret, query_edge(0, 0, 262143, in[top[u]], in[u]));
        u = par[top[u]];
    }
    ret = max(ret, query_edge(0, 0, 262143, min(in[u], in[v]), max(in[u], in[v])));
    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);
    dfs_edge(0);
    for (int i = 0; i < n; i++) sp[0][i] = par[i];
    for (int t = 1; t < 18; t++) for (int i = 0; i < n; i++) {
        if (sp[t - 1][i] == -1) sp[t][i] = -1;
        else sp[t][i] = sp[t - 1][sp[t - 1][i]];
    }
    for (int i = 0; i < n; i++) {
        tree_dist[262143 + in[i]] = dist[i];
        tree_edge[262143 + in[i]] = edge[i];
    }
    for (int i = 262142; i >= 0; i--) {
        tree_dist[i] = max(tree_dist[i * 2 + 1], tree_dist[i * 2 + 2]);
        tree_edge[i] = max(tree_edge[i * 2 + 1], tree_edge[i * 2 + 2]);
    }
    for (int i = 0; i < n; i++) for (auto &j: child[i]) lt_depth[i].insert(max_depth[j]);
    int zero = 2 * (n - 1) - dist[0], one = (int)1e9;
    for (int i = 0; i < n; i++) {
        dfs(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 x = j.first, pv = -1;
            vector<pair<int, int>> v;
            int y = max(rev_dist[l] - 1, query_hld_dist(i, j.first, in[l], in[l] + sz[l] - 1) - 1), T = 0;
            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 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]));
                if (B != -1) lt_depth[l].erase(lt_depth[l].find(max_depth[B]));
                if (!lt_depth[l].empty()) y = max(y, *lt_depth[l].rbegin() + rev_max_depth[l] - 1);
                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]);
                if (B != -1) lt_depth[l].insert(max_depth[B]);
            }
            if (Ap != -1) y = max(y, query_hld_edge(Ap, i) - 1);
            if (Bp != -1) y = max(y, query_hld_edge(Bp, j.first) - 1);
            while (x != -1) {
                for (auto &k: tree[x]) if (k != pv && k != _par[x]) {
                    if (_sz[k]) {
                        if (!v.empty() && v.back().second == T) {
                            y = max(y, v.back().first + _sz[k] - 1);
                            v.back().first = max(v.back().first, _sz[k]);
                        } else v.push_back({ _sz[k], T });
                    }
                }
                T++;
                pv = x;
                x = _par[x];
            }
            int ans = -(int)1e9;
            for (int i = 0; i < (int)v.size(); i++) {
                if (i) ans -= v[i].second - v[i - 1].second;
                y = max(y, ans + v[i].first + 1);
                ans = max(ans, v[i].first);
            }
            curr -= y;
            one = min(one, curr);
        }
    }
    printf("%d", min(zero, one));
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct
16 Correct 12 ms 25932 KB Output is correct
17 Correct 12 ms 25932 KB Output is correct
18 Correct 12 ms 25968 KB Output is correct
19 Correct 13 ms 25932 KB Output is correct
20 Correct 13 ms 25932 KB Output is correct
21 Correct 15 ms 25932 KB Output is correct
22 Correct 16 ms 25932 KB Output is correct
23 Correct 13 ms 25932 KB Output is correct
24 Correct 12 ms 25932 KB Output is correct
25 Correct 13 ms 25932 KB Output is correct
26 Correct 12 ms 25968 KB Output is correct
27 Correct 12 ms 25932 KB Output is correct
28 Correct 12 ms 25932 KB Output is correct
29 Correct 13 ms 26132 KB Output is correct
30 Correct 12 ms 25932 KB Output is correct
31 Correct 13 ms 25932 KB Output is correct
32 Correct 12 ms 25932 KB Output is correct
33 Correct 12 ms 25932 KB Output is correct
34 Correct 12 ms 25932 KB Output is correct
35 Correct 17 ms 25932 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 28768 KB Output is correct
2 Correct 831 ms 29188 KB Output is correct
3 Correct 738 ms 28272 KB Output is correct
4 Correct 676 ms 27876 KB Output is correct
5 Correct 754 ms 27760 KB Output is correct
6 Correct 309 ms 27448 KB Output is correct
7 Correct 834 ms 28968 KB Output is correct
8 Correct 843 ms 28492 KB Output is correct
9 Correct 795 ms 28976 KB Output is correct
10 Correct 683 ms 27800 KB Output is correct
11 Correct 699 ms 28416 KB Output is correct
12 Correct 671 ms 27632 KB Output is correct
13 Correct 677 ms 28104 KB Output is correct
14 Correct 674 ms 28176 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct
16 Correct 12 ms 25932 KB Output is correct
17 Correct 12 ms 25932 KB Output is correct
18 Correct 12 ms 25968 KB Output is correct
19 Correct 13 ms 25932 KB Output is correct
20 Correct 13 ms 25932 KB Output is correct
21 Correct 15 ms 25932 KB Output is correct
22 Correct 16 ms 25932 KB Output is correct
23 Correct 13 ms 25932 KB Output is correct
24 Correct 12 ms 25932 KB Output is correct
25 Correct 13 ms 25932 KB Output is correct
26 Correct 12 ms 25968 KB Output is correct
27 Correct 12 ms 25932 KB Output is correct
28 Correct 12 ms 25932 KB Output is correct
29 Correct 13 ms 26132 KB Output is correct
30 Correct 12 ms 25932 KB Output is correct
31 Correct 13 ms 25932 KB Output is correct
32 Correct 12 ms 25932 KB Output is correct
33 Correct 12 ms 25932 KB Output is correct
34 Correct 12 ms 25932 KB Output is correct
35 Correct 17 ms 25932 KB Output is correct
36 Correct 12 ms 26040 KB Output is correct
37 Correct 12 ms 26024 KB Output is correct
38 Correct 12 ms 25932 KB Output is correct
39 Correct 13 ms 25932 KB Output is correct
40 Correct 14 ms 25932 KB Output is correct
41 Correct 14 ms 25932 KB Output is correct
42 Correct 17 ms 25932 KB Output is correct
43 Correct 12 ms 26036 KB Output is correct
44 Correct 17 ms 25932 KB Output is correct
45 Correct 13 ms 26028 KB Output is correct
46 Correct 13 ms 25912 KB Output is correct
47 Correct 13 ms 25912 KB Output is correct
48 Correct 12 ms 25980 KB Output is correct
49 Correct 13 ms 25904 KB Output is correct

Subtask #5
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct
16 Correct 12 ms 25932 KB Output is correct
17 Correct 12 ms 25932 KB Output is correct
18 Correct 12 ms 25968 KB Output is correct
19 Correct 13 ms 25932 KB Output is correct
20 Correct 13 ms 25932 KB Output is correct
21 Correct 15 ms 25932 KB Output is correct
22 Correct 16 ms 25932 KB Output is correct
23 Correct 13 ms 25932 KB Output is correct
24 Correct 12 ms 25932 KB Output is correct
25 Correct 13 ms 25932 KB Output is correct
26 Correct 12 ms 25968 KB Output is correct
27 Correct 12 ms 25932 KB Output is correct
28 Correct 12 ms 25932 KB Output is correct
29 Correct 13 ms 26132 KB Output is correct
30 Correct 12 ms 25932 KB Output is correct
31 Correct 13 ms 25932 KB Output is correct
32 Correct 12 ms 25932 KB Output is correct
33 Correct 12 ms 25932 KB Output is correct
34 Correct 12 ms 25932 KB Output is correct
35 Correct 17 ms 25932 KB Output is correct
36 Correct 12 ms 26040 KB Output is correct
37 Correct 12 ms 26024 KB Output is correct
38 Correct 12 ms 25932 KB Output is correct
39 Correct 13 ms 25932 KB Output is correct
40 Correct 14 ms 25932 KB Output is correct
41 Correct 14 ms 25932 KB Output is correct
42 Correct 17 ms 25932 KB Output is correct
43 Correct 12 ms 26036 KB Output is correct
44 Correct 17 ms 25932 KB Output is correct
45 Correct 13 ms 26028 KB Output is correct
46 Correct 13 ms 25912 KB Output is correct
47 Correct 13 ms 25912 KB Output is correct
48 Correct 12 ms 25980 KB Output is correct
49 Correct 13 ms 25904 KB Output is correct
50 Correct 17 ms 26204 KB Output is correct
51 Correct 18 ms 26272 KB Output is correct
52 Correct 21 ms 26216 KB Output is correct
53 Correct 17 ms 26060 KB Output is correct
54 Correct 19 ms 26164 KB Output is correct
55 Correct 18 ms 26116 KB Output is correct
56 Correct 18 ms 26172 KB Output is correct
57 Correct 24 ms 26224 KB Output is correct
58 Correct 19 ms 26212 KB Output is correct
59 Correct 17 ms 26184 KB Output is correct
60 Correct 18 ms 26060 KB Output is correct
61 Correct 18 ms 26180 KB Output is correct
62 Correct 17 ms 26060 KB Output is correct
63 Correct 16 ms 26100 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct
16 Correct 12 ms 25932 KB Output is correct
17 Correct 12 ms 25932 KB Output is correct
18 Correct 12 ms 25968 KB Output is correct
19 Correct 13 ms 25932 KB Output is correct
20 Correct 13 ms 25932 KB Output is correct
21 Correct 15 ms 25932 KB Output is correct
22 Correct 16 ms 25932 KB Output is correct
23 Correct 13 ms 25932 KB Output is correct
24 Correct 12 ms 25932 KB Output is correct
25 Correct 13 ms 25932 KB Output is correct
26 Correct 12 ms 25968 KB Output is correct
27 Correct 12 ms 25932 KB Output is correct
28 Correct 12 ms 25932 KB Output is correct
29 Correct 13 ms 26132 KB Output is correct
30 Correct 12 ms 25932 KB Output is correct
31 Correct 13 ms 25932 KB Output is correct
32 Correct 12 ms 25932 KB Output is correct
33 Correct 12 ms 25932 KB Output is correct
34 Correct 12 ms 25932 KB Output is correct
35 Correct 17 ms 25932 KB Output is correct
36 Correct 821 ms 28768 KB Output is correct
37 Correct 831 ms 29188 KB Output is correct
38 Correct 738 ms 28272 KB Output is correct
39 Correct 676 ms 27876 KB Output is correct
40 Correct 754 ms 27760 KB Output is correct
41 Correct 309 ms 27448 KB Output is correct
42 Correct 834 ms 28968 KB Output is correct
43 Correct 843 ms 28492 KB Output is correct
44 Correct 795 ms 28976 KB Output is correct
45 Correct 683 ms 27800 KB Output is correct
46 Correct 699 ms 28416 KB Output is correct
47 Correct 671 ms 27632 KB Output is correct
48 Correct 677 ms 28104 KB Output is correct
49 Correct 674 ms 28176 KB Output is correct
50 Correct 12 ms 26040 KB Output is correct
51 Correct 12 ms 26024 KB Output is correct
52 Correct 12 ms 25932 KB Output is correct
53 Correct 13 ms 25932 KB Output is correct
54 Correct 14 ms 25932 KB Output is correct
55 Correct 14 ms 25932 KB Output is correct
56 Correct 17 ms 25932 KB Output is correct
57 Correct 12 ms 26036 KB Output is correct
58 Correct 17 ms 25932 KB Output is correct
59 Correct 13 ms 26028 KB Output is correct
60 Correct 13 ms 25912 KB Output is correct
61 Correct 13 ms 25912 KB Output is correct
62 Correct 12 ms 25980 KB Output is correct
63 Correct 13 ms 25904 KB Output is correct
64 Correct 17 ms 26204 KB Output is correct
65 Correct 18 ms 26272 KB Output is correct
66 Correct 21 ms 26216 KB Output is correct
67 Correct 17 ms 26060 KB Output is correct
68 Correct 19 ms 26164 KB Output is correct
69 Correct 18 ms 26116 KB Output is correct
70 Correct 18 ms 26172 KB Output is correct
71 Correct 24 ms 26224 KB Output is correct
72 Correct 19 ms 26212 KB Output is correct
73 Correct 17 ms 26184 KB Output is correct
74 Correct 18 ms 26060 KB Output is correct
75 Correct 18 ms 26180 KB Output is correct
76 Correct 17 ms 26060 KB Output is correct
77 Correct 16 ms 26100 KB Output is correct
78 Correct 799 ms 28320 KB Output is correct
79 Correct 798 ms 28612 KB Output is correct
80 Correct 753 ms 28128 KB Output is correct
81 Correct 798 ms 28108 KB Output is correct
82 Correct 695 ms 27724 KB Output is correct
83 Correct 296 ms 27444 KB Output is correct
84 Correct 831 ms 28400 KB Output is correct
85 Correct 788 ms 28576 KB Output is correct
86 Correct 803 ms 28772 KB Output is correct
87 Correct 710 ms 28040 KB Output is correct
88 Correct 682 ms 28056 KB Output is correct
89 Correct 746 ms 27868 KB Output is correct
90 Correct 656 ms 27756 KB Output is correct
91 Correct 577 ms 28012 KB Output is correct

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct
16 Correct 12 ms 25932 KB Output is correct
17 Correct 12 ms 25932 KB Output is correct
18 Correct 12 ms 25968 KB Output is correct
19 Correct 13 ms 25932 KB Output is correct
20 Correct 13 ms 25932 KB Output is correct
21 Correct 15 ms 25932 KB Output is correct
22 Correct 16 ms 25932 KB Output is correct
23 Correct 13 ms 25932 KB Output is correct
24 Correct 12 ms 25932 KB Output is correct
25 Correct 13 ms 25932 KB Output is correct
26 Correct 12 ms 25968 KB Output is correct
27 Correct 12 ms 25932 KB Output is correct
28 Correct 12 ms 25932 KB Output is correct
29 Correct 13 ms 26132 KB Output is correct
30 Correct 12 ms 25932 KB Output is correct
31 Correct 13 ms 25932 KB Output is correct
32 Correct 12 ms 25932 KB Output is correct
33 Correct 12 ms 25932 KB Output is correct
34 Correct 12 ms 25932 KB Output is correct
35 Correct 17 ms 25932 KB Output is correct
36 Correct 821 ms 28768 KB Output is correct
37 Correct 831 ms 29188 KB Output is correct
38 Correct 738 ms 28272 KB Output is correct
39 Correct 676 ms 27876 KB Output is correct
40 Correct 754 ms 27760 KB Output is correct
41 Correct 309 ms 27448 KB Output is correct
42 Correct 834 ms 28968 KB Output is correct
43 Correct 843 ms 28492 KB Output is correct
44 Correct 795 ms 28976 KB Output is correct
45 Correct 683 ms 27800 KB Output is correct
46 Correct 699 ms 28416 KB Output is correct
47 Correct 671 ms 27632 KB Output is correct
48 Correct 677 ms 28104 KB Output is correct
49 Correct 674 ms 28176 KB Output is correct
50 Correct 12 ms 26040 KB Output is correct
51 Correct 12 ms 26024 KB Output is correct
52 Correct 12 ms 25932 KB Output is correct
53 Correct 13 ms 25932 KB Output is correct
54 Correct 14 ms 25932 KB Output is correct
55 Correct 14 ms 25932 KB Output is correct
56 Correct 17 ms 25932 KB Output is correct
57 Correct 12 ms 26036 KB Output is correct
58 Correct 17 ms 25932 KB Output is correct
59 Correct 13 ms 26028 KB Output is correct
60 Correct 13 ms 25912 KB Output is correct
61 Correct 13 ms 25912 KB Output is correct
62 Correct 12 ms 25980 KB Output is correct
63 Correct 13 ms 25904 KB Output is correct
64 Correct 17 ms 26204 KB Output is correct
65 Correct 18 ms 26272 KB Output is correct
66 Correct 21 ms 26216 KB Output is correct
67 Correct 17 ms 26060 KB Output is correct
68 Correct 19 ms 26164 KB Output is correct
69 Correct 18 ms 26116 KB Output is correct
70 Correct 18 ms 26172 KB Output is correct
71 Correct 24 ms 26224 KB Output is correct
72 Correct 19 ms 26212 KB Output is correct
73 Correct 17 ms 26184 KB Output is correct
74 Correct 18 ms 26060 KB Output is correct
75 Correct 18 ms 26180 KB Output is correct
76 Correct 17 ms 26060 KB Output is correct
77 Correct 16 ms 26100 KB Output is correct
78 Correct 799 ms 28320 KB Output is correct
79 Correct 798 ms 28612 KB Output is correct
80 Correct 753 ms 28128 KB Output is correct
81 Correct 798 ms 28108 KB Output is correct
82 Correct 695 ms 27724 KB Output is correct
83 Correct 296 ms 27444 KB Output is correct
84 Correct 831 ms 28400 KB Output is correct
85 Correct 788 ms 28576 KB Output is correct
86 Correct 803 ms 28772 KB Output is correct
87 Correct 710 ms 28040 KB Output is correct
88 Correct 682 ms 28056 KB Output is correct
89 Correct 746 ms 27868 KB Output is correct
90 Correct 656 ms 27756 KB Output is correct
91 Correct 577 ms 28012 KB Output is correct
92 Execution timed out 7041 ms 58112 KB Time limit exceeded
93 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25932 KB Output is correct
2 Correct 12 ms 25932 KB Output is correct
3 Correct 13 ms 25932 KB Output is correct
4 Correct 13 ms 25932 KB Output is correct
5 Correct 13 ms 25932 KB Output is correct
6 Correct 13 ms 25920 KB Output is correct
7 Correct 14 ms 25932 KB Output is correct
8 Correct 17 ms 25988 KB Output is correct
9 Correct 13 ms 25932 KB Output is correct
10 Correct 13 ms 25932 KB Output is correct
11 Correct 12 ms 26004 KB Output is correct
12 Correct 12 ms 25996 KB Output is correct
13 Correct 12 ms 25956 KB Output is correct
14 Correct 13 ms 25964 KB Output is correct
15 Correct 12 ms 25932 KB Output is correct
16 Correct 12 ms 25932 KB Output is correct
17 Correct 12 ms 25932 KB Output is correct
18 Correct 12 ms 25968 KB Output is correct
19 Correct 13 ms 25932 KB Output is correct
20 Correct 13 ms 25932 KB Output is correct
21 Correct 15 ms 25932 KB Output is correct
22 Correct 16 ms 25932 KB Output is correct
23 Correct 13 ms 25932 KB Output is correct
24 Correct 12 ms 25932 KB Output is correct
25 Correct 13 ms 25932 KB Output is correct
26 Correct 12 ms 25968 KB Output is correct
27 Correct 12 ms 25932 KB Output is correct
28 Correct 12 ms 25932 KB Output is correct
29 Correct 13 ms 26132 KB Output is correct
30 Correct 12 ms 25932 KB Output is correct
31 Correct 13 ms 25932 KB Output is correct
32 Correct 12 ms 25932 KB Output is correct
33 Correct 12 ms 25932 KB Output is correct
34 Correct 12 ms 25932 KB Output is correct
35 Correct 17 ms 25932 KB Output is correct
36 Correct 821 ms 28768 KB Output is correct
37 Correct 831 ms 29188 KB Output is correct
38 Correct 738 ms 28272 KB Output is correct
39 Correct 676 ms 27876 KB Output is correct
40 Correct 754 ms 27760 KB Output is correct
41 Correct 309 ms 27448 KB Output is correct
42 Correct 834 ms 28968 KB Output is correct
43 Correct 843 ms 28492 KB Output is correct
44 Correct 795 ms 28976 KB Output is correct
45 Correct 683 ms 27800 KB Output is correct
46 Correct 699 ms 28416 KB Output is correct
47 Correct 671 ms 27632 KB Output is correct
48 Correct 677 ms 28104 KB Output is correct
49 Correct 674 ms 28176 KB Output is correct
50 Correct 12 ms 26040 KB Output is correct
51 Correct 12 ms 26024 KB Output is correct
52 Correct 12 ms 25932 KB Output is correct
53 Correct 13 ms 25932 KB Output is correct
54 Correct 14 ms 25932 KB Output is correct
55 Correct 14 ms 25932 KB Output is correct
56 Correct 17 ms 25932 KB Output is correct
57 Correct 12 ms 26036 KB Output is correct
58 Correct 17 ms 25932 KB Output is correct
59 Correct 13 ms 26028 KB Output is correct
60 Correct 13 ms 25912 KB Output is correct
61 Correct 13 ms 25912 KB Output is correct
62 Correct 12 ms 25980 KB Output is correct
63 Correct 13 ms 25904 KB Output is correct
64 Correct 17 ms 26204 KB Output is correct
65 Correct 18 ms 26272 KB Output is correct
66 Correct 21 ms 26216 KB Output is correct
67 Correct 17 ms 26060 KB Output is correct
68 Correct 19 ms 26164 KB Output is correct
69 Correct 18 ms 26116 KB Output is correct
70 Correct 18 ms 26172 KB Output is correct
71 Correct 24 ms 26224 KB Output is correct
72 Correct 19 ms 26212 KB Output is correct
73 Correct 17 ms 26184 KB Output is correct
74 Correct 18 ms 26060 KB Output is correct
75 Correct 18 ms 26180 KB Output is correct
76 Correct 17 ms 26060 KB Output is correct
77 Correct 16 ms 26100 KB Output is correct
78 Correct 799 ms 28320 KB Output is correct
79 Correct 798 ms 28612 KB Output is correct
80 Correct 753 ms 28128 KB Output is correct
81 Correct 798 ms 28108 KB Output is correct
82 Correct 695 ms 27724 KB Output is correct
83 Correct 296 ms 27444 KB Output is correct
84 Correct 831 ms 28400 KB Output is correct
85 Correct 788 ms 28576 KB Output is correct
86 Correct 803 ms 28772 KB Output is correct
87 Correct 710 ms 28040 KB Output is correct
88 Correct 682 ms 28056 KB Output is correct
89 Correct 746 ms 27868 KB Output is correct
90 Correct 656 ms 27756 KB Output is correct
91 Correct 577 ms 28012 KB Output is correct
92 Execution timed out 7041 ms 58112 KB Time limit exceeded
93 Halted 0 ms 0 KB -