oj.uz

답안 #1056659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056659 2024-08-13T10:30:12 Z mickey080929 Summer Driving (CCO24_day1problem3) C++17
23 / 25
 6000 ms 617592 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const int inf = 1e9;

struct SegmentTree{
    vector<int> tree;
    void init(int n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, inf);
    }
    void update(int node, int s, int e, int l, int r, int val) {
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            tree[node] = min(tree[node], val);
            return;
        }
        int mid = s + e >> 1;
        update(node*2, s, mid, l, r, val);
        update(node*2+1, mid+1, e, l, r, val);
    }
    int query(int node, int s, int e, int tar) {
        if (s == e) return tree[node];
        int mid = s + e >> 1;
        if (tar <= mid) return min(tree[node], query(node*2, s, mid, tar));
        return min(tree[node], query(node*2+1, mid+1, e, tar));
    }
};

struct MN2{
    pair<int,int> val1, val2;
};

struct Node{
    int l, r;
    MN2 val;
};

MN2 Merge(MN2 u, MN2 v) {
    MN2 ret;
    if (u.val1 > v.val1) swap(u, v);
    ret.val1 = u.val1;
    ret.val2 = u.val2;
    if (v.val1.second != ret.val1.second && ret.val2 > v.val1)
        ret.val2 = v.val1;
    if (v.val2.second != ret.val1.second && ret.val2 > v.val2)
        ret.val2 = v.val2;
    return ret;
}

struct DynamicSegmentTree{
    vector<Node> tree;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
    }
    void update(int node, int s, int e, int tar, pair<int,int> val) {
        tree[node].val = Merge(tree[node].val, {val, {inf,-1}});
        if (s == e) {    
            return;
        }
        int mid = s + e >> 1;
        if (tar <= mid) {
            if (tree[node].l == -1) {
                tree[node].l = tree.size();
                tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
            }
            update(tree[node].l, s, mid, tar, val);
        }
        else {
            if (tree[node].r == -1) {
                tree[node].r = tree.size();
                tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
            }
            update(tree[node].r, mid+1, e, tar, val);
        }
    }
    MN2 query(int node, int s, int e, int l, int r, bool f = false) {
        if (l > e || s > r || node == -1) return {{inf,-1}, {inf,-1}};
        if (l <= s && e <= r) return tree[node].val;
        int mid = s + e >> 1;
        return Merge(query(tree[node].l, s, mid, l, r, f), query(tree[node].r, mid+1, e, l, r, f));
    }
};

SegmentTree seg;

int N, R, A, B;
vector<int> adj[300010];
vector<int> g[300010];
int down[300010], par[300010];
int dep[300010];
int in[300010], out[300010];
int pv;
int sz[300010];
int top[300010];

int chk[300010];

int getSize(int x, int p) {
    sz[x] = 1;
    for (auto &y : adj[x]) {
        if (chk[y] || y == p) continue;
        sz[x] += getSize(y, x);
    }
    return sz[x];
}

int getCent(int x, int p, int cap) {
    for (auto &y : adj[x]) {
        if (chk[y] || y == p) continue;
        if (sz[y] * 2 > cap)
            return getCent(y, x, cap);
    }
    return x;
}

set<int> ps[300010];
int cent[300010][20], dist[300010][20];
int sub[300010][20];

void dfs3(int x, int p, int lv, int S) {
    sub[x][lv] = S;
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        cent[y][lv] = cent[x][lv];
        dist[y][lv] = dist[x][lv] + 1;
        dfs3(y, x, lv, S);
    }
}

void dnc(int x, int lv) {
    x = getCent(x, -1, getSize(x, -1));
    int t = x;
    while (t && !chk[t]) {
        ps[x].insert(t);
        t = par[t];
    }
    sub[x][lv] = x;
    cent[x][lv] = x;
    dist[x][lv] = 0;
    for (auto &y : adj[x]) {
        if (chk[y]) continue;
        cent[y][lv] = x;
        dist[y][lv] = 1;
        dfs3(y, x, lv, y);
    }
    chk[x] = 1;
    for (auto &y : adj[x]) {
        if (chk[y]) continue;
        dnc(y, lv+1);
    }
}

void dfs(int x, int p) {
    sz[x] = 1;
    down[x] = 0;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        par[y] = x;
        dep[y] = dep[x] + 1;
        g[x].push_back(y);
        dfs(y, x);
        down[x] = max(down[x], down[y] + 1);
        if (sz[g[x][0]] < sz[y]) swap(g[x][0], g[x].back());
        sz[x] += sz[y];
    }
}

void dfs2(int x) {
    in[x] = ++ pv;
    for (auto &y : g[x]) {
        top[y] = y == g[x][0] ? top[x] : y;
        dfs2(y);
    }
    out[x] = pv;
}

void HLDupdate(int x) {
    int ori = x;
    int cnt = B;
    while (x) {
        int tp = top[x];
        if (dep[x] - dep[tp] + 1 < cnt) {
            seg.update(1, 1, N, in[tp], in[x], ori);
            cnt -= dep[x] - dep[tp] + 1;
        }
        else {
            seg.update(1, 1, N, in[x]-cnt+1, in[x], ori);
            break;
        }
        x = par[tp];
    }
}

int dp[300010];
int dp2[300010];

vector<int> vtx[300010];
vector<pair<int,int>> poss[300010], imp[300010];
DynamicSegmentTree seg1[300010], seg2[300010];

void CentUpdate(int x) {
    for (int lv=19; lv>=0; lv--) {
        if (!cent[x][lv]) continue;
        if (cent[x][lv] == x) continue;
        int c = cent[x][lv];
        int val;
        if (poss[x].empty()) val = imp[x][0].first;
        else val = poss[x][0].first;
        if (sub[x][lv] == par[c]) {
            if (ps[c].find(x) != ps[c].end()) {
                if (poss[x].empty()) {
                    if (ps[c].find(imp[x][0].second) != ps[c].end())
                        val = imp[x][1].first;
                }
                else if (poss[x].size() == 1) {
                    if (ps[c].find(poss[x][0].second) != ps[c].end())
                        val = imp[x][0].first;
                }
                else {
                    if (ps[c].find(poss[x][0].second) != ps[c].end())
                        val = poss[x][1].first;
                }
            }
            seg1[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
        }
        else {
            seg1[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
        }
        
    }
}

int Centquery(int x) {
    int ret = N + 1;
    for (int lv=19; lv>=0; lv--) {
        if (!cent[x][lv]) continue;
        int d = B - dist[x][lv];
        if (d < 0) continue;
        int c = cent[x][lv];
        int val;
        if (poss[c].empty()) val = imp[c][0].first;
        else val = poss[c][0].first;
        if (x == c) {
            ret = min(ret, val);
        }
        else {
            if (poss[c].empty()) {
                if (sub[x][lv] == imp[c][0].second)
                    val = imp[c][1].first;
            }
            else if (poss[c].size() == 1) {
                if (sub[x][lv] == poss[c][0].second)
                    val = imp[c][0].first;
            }
            else {
                if (sub[x][lv] == poss[c][0].second)
                    val = poss[c][1].first;
            }
            ret = min(ret, val);
        }
        if (d == 0) continue;
        MN2 t = seg1[c].query(0, 1, N, 1, d);
        //assert(t.val1.second != t.val2.second);
        if (t.val1.second == sub[x][lv]) ret = min(ret, t.val2.first);
        else ret = min(ret, t.val1.first);
    }
    assert(ret != N+1);
    return ret;
}

//DynamicSegmentTree final[300010];

int simulate(int x, int p, int dist) {
    if (dist > B) return N + 1;
    int ret;
    int d = 0;
    for (auto &y : adj[x]) {
        if (y == p || y == par[x]) continue;
        d = max(d, down[y] + 1);
    }
    if (d < A) {
        ret = x;
        for (auto &y : adj[x]) {
            if (y == p || y == par[x]) continue;
            ret = min(ret, dp[y]);
        }
    }
    else {
        ret = 0;
        for (auto &y : adj[x]) {
            if (y == p || y == par[x]) continue;
            if (down[y] >= A-1)
                ret = max(ret, dp[y]);
        }
    }
    for (auto &y : adj[x]) {
        if (y == p) continue;
        ret = min(ret, simulate(y, x, dist + 1));
    }
    return ret;
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> R >> A >> B;
    if (A <= B) {
        cout << "1\n";
        return 0;
    }
    for (int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(R, 0);
    top[R] = R;
    dfs2(R);
    seg.init(N);
    int mxdep = 0;
    for (int i=1; i<=N; i++) {
        mxdep = max(mxdep, dep[i]);
        vtx[dep[i]].push_back(i);
        HLDupdate(i);
        imp[i].push_back({i, -1});
        seg1[i].init();
        seg2[i].init();
    }
    dnc(1, 0);
    for (int i=mxdep; i>=1; i--) {
        for (auto &x : vtx[i]) {
            sort(imp[x].begin(), imp[x].end());
            sort(poss[x].begin(), poss[x].end());
            reverse(poss[x].begin(), poss[x].end());
            CentUpdate(x);
        }
        if (i+A-1 <= mxdep) {
            for (auto &x : vtx[i+A-1]) {
                int ret1 = Centquery(x);
                //  assert(ret1 <= ret2);
                dp2[x] = ret1;
            }
        }
        for (auto &x : vtx[i]) {
            if (down[x] < A-1) {
                dp[x] = min(par[x], seg.query(1, 1, N, in[x]));
                imp[par[x]].push_back({dp[x], x});
            }
            else {
                for (auto &y : vtx[i+A-1]) {
                    if (in[x] <= in[y] && in[y] <= out[x])
                        dp[x] = max(dp[x], dp2[y]);
                }
                poss[par[x]].push_back({dp[x], x});
            }
            //cout << i << ' ' << dp[x] << ' ' << x << '\n';
        }
        
    }
    if (down[R] < A) {
        int ans = R;
        for (auto &x : vtx[1]) {
            ans = min(ans, dp[x]);
        }
        cout << ans;
    }
    else {
        int ans = 0;
        for (auto &x : vtx[1]) {
            if (down[x] >= A-1)
                ans = max(ans, dp[x]);
        }
        cout << ans;
    }
}

Compilation message

Main.cpp: In member function 'void SegmentTree::init(int)':
Main.cpp:12:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
Main.cpp:21:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
Main.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void DynamicSegmentTree::update(int, int, int, int, std::pair<int, int>)':
Main.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'MN2 DynamicSegmentTree::query(int, int, int, int, int, bool)':
Main.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 67932 KB Output is correct
2 Correct 9 ms 67932 KB Output is correct
3 Correct 9 ms 67932 KB Output is correct
4 Correct 9 ms 67880 KB Output is correct
5 Correct 9 ms 68032 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2871 ms 615636 KB Output is correct
2 Correct 2726 ms 616744 KB Output is correct
3 Correct 1859 ms 614908 KB Output is correct
4 Correct 1868 ms 613372 KB Output is correct
5 Correct 2932 ms 596032 KB Output is correct
6 Correct 2661 ms 613324 KB Output is correct
7 Correct 3071 ms 614124 KB Output is correct
8 Correct 3039 ms 615696 KB Output is correct
9 Correct 9 ms 67928 KB Output is correct
10 Correct 2817 ms 616264 KB Output is correct
11 Correct 2833 ms 617592 KB Output is correct
12 Correct 12 ms 67932 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 80472 KB Output is correct
2 Correct 13 ms 80476 KB Output is correct
3 Correct 11 ms 80476 KB Output is correct
4 Correct 16 ms 80544 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 12 ms 80544 KB Output is correct
7 Correct 13 ms 80476 KB Output is correct
8 Correct 10 ms 80328 KB Output is correct
9 Correct 10 ms 67932 KB Output is correct
10 Correct 14 ms 80560 KB Output is correct
11 Correct 14 ms 80476 KB Output is correct
12 Correct 13 ms 80216 KB Output is correct
13 Correct 14 ms 80220 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 80472 KB Output is correct
2 Correct 13 ms 80476 KB Output is correct
3 Correct 11 ms 80476 KB Output is correct
4 Correct 16 ms 80544 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 12 ms 80544 KB Output is correct
7 Correct 13 ms 80476 KB Output is correct
8 Correct 10 ms 80328 KB Output is correct
9 Correct 10 ms 67932 KB Output is correct
10 Correct 14 ms 80560 KB Output is correct
11 Correct 14 ms 80476 KB Output is correct
12 Correct 13 ms 80216 KB Output is correct
13 Correct 14 ms 80220 KB Output is correct
14 Correct 21 ms 81496 KB Output is correct
15 Correct 23 ms 81636 KB Output is correct
16 Correct 18 ms 81500 KB Output is correct
17 Correct 22 ms 81756 KB Output is correct
18 Correct 18 ms 81496 KB Output is correct
19 Correct 23 ms 81752 KB Output is correct
20 Correct 18 ms 81756 KB Output is correct
21 Correct 16 ms 81456 KB Output is correct
22 Correct 9 ms 68068 KB Output is correct
23 Correct 16 ms 81500 KB Output is correct
24 Correct 17 ms 81936 KB Output is correct
25 Correct 17 ms 81960 KB Output is correct
26 Correct 18 ms 81752 KB Output is correct
27 Correct 12 ms 80988 KB Output is correct
28 Correct 14 ms 80988 KB Output is correct
29 Correct 13 ms 81132 KB Output is correct
30 Correct 17 ms 81252 KB Output is correct
31 Correct 17 ms 81220 KB Output is correct
32 Correct 14 ms 81244 KB Output is correct
33 Correct 25 ms 83428 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1188 ms 157376 KB Output is correct
2 Correct 1025 ms 163968 KB Output is correct
3 Correct 789 ms 158836 KB Output is correct
4 Correct 813 ms 164036 KB Output is correct
5 Correct 1014 ms 158804 KB Output is correct
6 Correct 934 ms 163748 KB Output is correct
7 Correct 528 ms 163160 KB Output is correct
8 Correct 260 ms 150100 KB Output is correct
9 Correct 548 ms 163708 KB Output is correct
10 Correct 489 ms 165716 KB Output is correct
11 Correct 396 ms 165204 KB Output is correct
12 Correct 218 ms 141992 KB Output is correct
13 Correct 10 ms 68068 KB Output is correct
14 Correct 10 ms 68084 KB Output is correct
15 Correct 402 ms 157620 KB Output is correct
16 Correct 136 ms 135688 KB Output is correct
17 Correct 135 ms 138320 KB Output is correct
18 Correct 177 ms 136580 KB Output is correct
19 Correct 745 ms 255852 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 80472 KB Output is correct
2 Correct 13 ms 80476 KB Output is correct
3 Correct 11 ms 80476 KB Output is correct
4 Correct 16 ms 80544 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 12 ms 80544 KB Output is correct
7 Correct 13 ms 80476 KB Output is correct
8 Correct 10 ms 80328 KB Output is correct
9 Correct 10 ms 67932 KB Output is correct
10 Correct 14 ms 80560 KB Output is correct
11 Correct 14 ms 80476 KB Output is correct
12 Correct 13 ms 80216 KB Output is correct
13 Correct 14 ms 80220 KB Output is correct
14 Correct 21 ms 81496 KB Output is correct
15 Correct 23 ms 81636 KB Output is correct
16 Correct 18 ms 81500 KB Output is correct
17 Correct 22 ms 81756 KB Output is correct
18 Correct 18 ms 81496 KB Output is correct
19 Correct 23 ms 81752 KB Output is correct
20 Correct 18 ms 81756 KB Output is correct
21 Correct 16 ms 81456 KB Output is correct
22 Correct 9 ms 68068 KB Output is correct
23 Correct 16 ms 81500 KB Output is correct
24 Correct 17 ms 81936 KB Output is correct
25 Correct 17 ms 81960 KB Output is correct
26 Correct 18 ms 81752 KB Output is correct
27 Correct 12 ms 80988 KB Output is correct
28 Correct 14 ms 80988 KB Output is correct
29 Correct 13 ms 81132 KB Output is correct
30 Correct 17 ms 81252 KB Output is correct
31 Correct 17 ms 81220 KB Output is correct
32 Correct 14 ms 81244 KB Output is correct
33 Correct 25 ms 83428 KB Output is correct
34 Correct 1068 ms 157520 KB Output is correct
35 Correct 943 ms 163924 KB Output is correct
36 Correct 701 ms 157324 KB Output is correct
37 Correct 792 ms 163928 KB Output is correct
38 Correct 1010 ms 158804 KB Output is correct
39 Correct 870 ms 163924 KB Output is correct
40 Correct 545 ms 164564 KB Output is correct
41 Correct 235 ms 150232 KB Output is correct
42 Correct 9 ms 67932 KB Output is correct
43 Correct 446 ms 156028 KB Output is correct
44 Correct 146 ms 137040 KB Output is correct
45 Correct 155 ms 138256 KB Output is correct
46 Correct 194 ms 136908 KB Output is correct
47 Correct 328 ms 177512 KB Output is correct
48 Correct 768 ms 256464 KB Output is correct
49 Correct 477 ms 167508 KB Output is correct
50 Correct 432 ms 167160 KB Output is correct
51 Correct 401 ms 167452 KB Output is correct
52 Correct 137 ms 128176 KB Output is correct
53 Correct 169 ms 127052 KB Output is correct
54 Correct 129 ms 128588 KB Output is correct
55 Correct 690 ms 252600 KB Output is correct
56 Correct 692 ms 254828 KB Output is correct
57 Correct 420 ms 163504 KB Output is correct
58 Correct 625 ms 163536 KB Output is correct

Subtask #7
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 67932 KB Output is correct
2 Correct 9 ms 67932 KB Output is correct
3 Correct 9 ms 67932 KB Output is correct
4 Correct 9 ms 67880 KB Output is correct
5 Correct 9 ms 68032 KB Output is correct
6 Correct 2871 ms 615636 KB Output is correct
7 Correct 2726 ms 616744 KB Output is correct
8 Correct 1859 ms 614908 KB Output is correct
9 Correct 1868 ms 613372 KB Output is correct
10 Correct 2932 ms 596032 KB Output is correct
11 Correct 2661 ms 613324 KB Output is correct
12 Correct 3071 ms 614124 KB Output is correct
13 Correct 3039 ms 615696 KB Output is correct
14 Correct 9 ms 67928 KB Output is correct
15 Correct 2817 ms 616264 KB Output is correct
16 Correct 2833 ms 617592 KB Output is correct
17 Correct 12 ms 67932 KB Output is correct
18 Correct 15 ms 80472 KB Output is correct
19 Correct 13 ms 80476 KB Output is correct
20 Correct 11 ms 80476 KB Output is correct
21 Correct 16 ms 80544 KB Output is correct
22 Correct 11 ms 80476 KB Output is correct
23 Correct 12 ms 80544 KB Output is correct
24 Correct 13 ms 80476 KB Output is correct
25 Correct 10 ms 80328 KB Output is correct
26 Correct 10 ms 67932 KB Output is correct
27 Correct 14 ms 80560 KB Output is correct
28 Correct 14 ms 80476 KB Output is correct
29 Correct 13 ms 80216 KB Output is correct
30 Correct 14 ms 80220 KB Output is correct
31 Correct 21 ms 81496 KB Output is correct
32 Correct 23 ms 81636 KB Output is correct
33 Correct 18 ms 81500 KB Output is correct
34 Correct 22 ms 81756 KB Output is correct
35 Correct 18 ms 81496 KB Output is correct
36 Correct 23 ms 81752 KB Output is correct
37 Correct 18 ms 81756 KB Output is correct
38 Correct 16 ms 81456 KB Output is correct
39 Correct 9 ms 68068 KB Output is correct
40 Correct 16 ms 81500 KB Output is correct
41 Correct 17 ms 81936 KB Output is correct
42 Correct 17 ms 81960 KB Output is correct
43 Correct 18 ms 81752 KB Output is correct
44 Correct 12 ms 80988 KB Output is correct
45 Correct 14 ms 80988 KB Output is correct
46 Correct 13 ms 81132 KB Output is correct
47 Correct 17 ms 81252 KB Output is correct
48 Correct 17 ms 81220 KB Output is correct
49 Correct 14 ms 81244 KB Output is correct
50 Correct 25 ms 83428 KB Output is correct
51 Correct 1188 ms 157376 KB Output is correct
52 Correct 1025 ms 163968 KB Output is correct
53 Correct 789 ms 158836 KB Output is correct
54 Correct 813 ms 164036 KB Output is correct
55 Correct 1014 ms 158804 KB Output is correct
56 Correct 934 ms 163748 KB Output is correct
57 Correct 528 ms 163160 KB Output is correct
58 Correct 260 ms 150100 KB Output is correct
59 Correct 548 ms 163708 KB Output is correct
60 Correct 489 ms 165716 KB Output is correct
61 Correct 396 ms 165204 KB Output is correct
62 Correct 218 ms 141992 KB Output is correct
63 Correct 10 ms 68068 KB Output is correct
64 Correct 10 ms 68084 KB Output is correct
65 Correct 402 ms 157620 KB Output is correct
66 Correct 136 ms 135688 KB Output is correct
67 Correct 135 ms 138320 KB Output is correct
68 Correct 177 ms 136580 KB Output is correct
69 Correct 745 ms 255852 KB Output is correct
70 Correct 1068 ms 157520 KB Output is correct
71 Correct 943 ms 163924 KB Output is correct
72 Correct 701 ms 157324 KB Output is correct
73 Correct 792 ms 163928 KB Output is correct
74 Correct 1010 ms 158804 KB Output is correct
75 Correct 870 ms 163924 KB Output is correct
76 Correct 545 ms 164564 KB Output is correct
77 Correct 235 ms 150232 KB Output is correct
78 Correct 9 ms 67932 KB Output is correct
79 Correct 446 ms 156028 KB Output is correct
80 Correct 146 ms 137040 KB Output is correct
81 Correct 155 ms 138256 KB Output is correct
82 Correct 194 ms 136908 KB Output is correct
83 Correct 328 ms 177512 KB Output is correct
84 Correct 768 ms 256464 KB Output is correct
85 Correct 477 ms 167508 KB Output is correct
86 Correct 432 ms 167160 KB Output is correct
87 Correct 401 ms 167452 KB Output is correct
88 Correct 137 ms 128176 KB Output is correct
89 Correct 169 ms 127052 KB Output is correct
90 Correct 129 ms 128588 KB Output is correct
91 Correct 690 ms 252600 KB Output is correct
92 Correct 692 ms 254828 KB Output is correct
93 Correct 420 ms 163504 KB Output is correct
94 Correct 625 ms 163536 KB Output is correct
95 Execution timed out 6074 ms 312944 KB Time limit exceeded
96 Halted 0 ms 0 KB -