oj.uz

답안 #1056676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056676 2024-08-13T10:34:41 Z mickey080929 Summer Driving (CCO24_day1problem3) C++17
25 / 25
 3251 ms 752000 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));
    }
};

struct Node2{
    int l, r, val;
};
 
struct DynamicSegmentTree2{
    vector<Node2> tree;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, -inf});
    }
    void update(int node, int s, int e, int tar, int val) {
        tree[node].val = max(tree[node].val, val);
        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});
            }
            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});
            }
            update(tree[node].r, mid+1, e, tar, val);
        }
    }
    int query(int node, int s, int e, int l, int r) {
        if (l > e || s > r || node == -1) return -inf;
        if (l <= s && e <= r) return tree[node].val;
        int mid = s + e >> 1;
        return max(query(tree[node].l, s, mid, l, r), query(tree[node].r, mid+1, e, l, r));
    }
};

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;
}

DynamicSegmentTree2 final[300010];

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();
        final[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;
                final[i+A-1].update(0, 1, N, in[x], dp2[x]);
            }
        }
        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 {
                dp[x] = final[i+A-1].query(0, 1, N, in[x], out[x]);
                poss[par[x]].push_back({dp[x], x});
            }
            
        }
        
    }
    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;
      |                   ~~^~~
Main.cpp: In member function 'void DynamicSegmentTree2::update(int, int, int, int, int)':
Main.cpp:104:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int DynamicSegmentTree2::query(int, int, int, int, int)':
Main.cpp:123:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 73048 KB Output is correct
2 Correct 11 ms 73052 KB Output is correct
3 Correct 11 ms 73092 KB Output is correct
4 Correct 11 ms 73052 KB Output is correct
5 Correct 12 ms 73048 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3039 ms 752000 KB Output is correct
2 Correct 3056 ms 747396 KB Output is correct
3 Correct 2195 ms 743600 KB Output is correct
4 Correct 2173 ms 733408 KB Output is correct
5 Correct 3251 ms 707324 KB Output is correct
6 Correct 2703 ms 631004 KB Output is correct
7 Correct 2603 ms 633416 KB Output is correct
8 Correct 2885 ms 689352 KB Output is correct
9 Correct 10 ms 73052 KB Output is correct
10 Correct 2893 ms 749028 KB Output is correct
11 Correct 2884 ms 748668 KB Output is correct
12 Correct 10 ms 73052 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 85340 KB Output is correct
2 Correct 11 ms 85404 KB Output is correct
3 Correct 11 ms 85336 KB Output is correct
4 Correct 11 ms 85340 KB Output is correct
5 Correct 12 ms 85336 KB Output is correct
6 Correct 11 ms 85340 KB Output is correct
7 Correct 12 ms 85380 KB Output is correct
8 Correct 11 ms 85348 KB Output is correct
9 Correct 10 ms 73052 KB Output is correct
10 Correct 11 ms 85576 KB Output is correct
11 Correct 12 ms 85596 KB Output is correct
12 Correct 11 ms 85404 KB Output is correct
13 Correct 11 ms 85332 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 85340 KB Output is correct
2 Correct 11 ms 85404 KB Output is correct
3 Correct 11 ms 85336 KB Output is correct
4 Correct 11 ms 85340 KB Output is correct
5 Correct 12 ms 85336 KB Output is correct
6 Correct 11 ms 85340 KB Output is correct
7 Correct 12 ms 85380 KB Output is correct
8 Correct 11 ms 85348 KB Output is correct
9 Correct 10 ms 73052 KB Output is correct
10 Correct 11 ms 85576 KB Output is correct
11 Correct 12 ms 85596 KB Output is correct
12 Correct 11 ms 85404 KB Output is correct
13 Correct 11 ms 85332 KB Output is correct
14 Correct 16 ms 86876 KB Output is correct
15 Correct 19 ms 86876 KB Output is correct
16 Correct 16 ms 86956 KB Output is correct
17 Correct 17 ms 87132 KB Output is correct
18 Correct 15 ms 86956 KB Output is correct
19 Correct 16 ms 87048 KB Output is correct
20 Correct 17 ms 87132 KB Output is correct
21 Correct 14 ms 86364 KB Output is correct
22 Correct 10 ms 72832 KB Output is correct
23 Correct 18 ms 86876 KB Output is correct
24 Correct 18 ms 87276 KB Output is correct
25 Correct 18 ms 87128 KB Output is correct
26 Correct 17 ms 86876 KB Output is correct
27 Correct 13 ms 86208 KB Output is correct
28 Correct 15 ms 86356 KB Output is correct
29 Correct 14 ms 86108 KB Output is correct
30 Correct 13 ms 86364 KB Output is correct
31 Correct 13 ms 86360 KB Output is correct
32 Correct 14 ms 86360 KB Output is correct
33 Correct 22 ms 89184 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 173352 KB Output is correct
2 Correct 415 ms 179288 KB Output is correct
3 Correct 353 ms 172264 KB Output is correct
4 Correct 400 ms 178052 KB Output is correct
5 Correct 334 ms 172216 KB Output is correct
6 Correct 418 ms 177848 KB Output is correct
7 Correct 477 ms 178972 KB Output is correct
8 Correct 259 ms 158488 KB Output is correct
9 Correct 487 ms 179920 KB Output is correct
10 Correct 465 ms 177448 KB Output is correct
11 Correct 364 ms 173436 KB Output is correct
12 Correct 210 ms 151500 KB Output is correct
13 Correct 10 ms 73048 KB Output is correct
14 Correct 9 ms 73052 KB Output is correct
15 Correct 431 ms 172808 KB Output is correct
16 Correct 155 ms 148752 KB Output is correct
17 Correct 171 ms 149956 KB Output is correct
18 Correct 156 ms 150012 KB Output is correct
19 Correct 786 ms 297588 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 85340 KB Output is correct
2 Correct 11 ms 85404 KB Output is correct
3 Correct 11 ms 85336 KB Output is correct
4 Correct 11 ms 85340 KB Output is correct
5 Correct 12 ms 85336 KB Output is correct
6 Correct 11 ms 85340 KB Output is correct
7 Correct 12 ms 85380 KB Output is correct
8 Correct 11 ms 85348 KB Output is correct
9 Correct 10 ms 73052 KB Output is correct
10 Correct 11 ms 85576 KB Output is correct
11 Correct 12 ms 85596 KB Output is correct
12 Correct 11 ms 85404 KB Output is correct
13 Correct 11 ms 85332 KB Output is correct
14 Correct 16 ms 86876 KB Output is correct
15 Correct 19 ms 86876 KB Output is correct
16 Correct 16 ms 86956 KB Output is correct
17 Correct 17 ms 87132 KB Output is correct
18 Correct 15 ms 86956 KB Output is correct
19 Correct 16 ms 87048 KB Output is correct
20 Correct 17 ms 87132 KB Output is correct
21 Correct 14 ms 86364 KB Output is correct
22 Correct 10 ms 72832 KB Output is correct
23 Correct 18 ms 86876 KB Output is correct
24 Correct 18 ms 87276 KB Output is correct
25 Correct 18 ms 87128 KB Output is correct
26 Correct 17 ms 86876 KB Output is correct
27 Correct 13 ms 86208 KB Output is correct
28 Correct 15 ms 86356 KB Output is correct
29 Correct 14 ms 86108 KB Output is correct
30 Correct 13 ms 86364 KB Output is correct
31 Correct 13 ms 86360 KB Output is correct
32 Correct 14 ms 86360 KB Output is correct
33 Correct 22 ms 89184 KB Output is correct
34 Correct 379 ms 172088 KB Output is correct
35 Correct 417 ms 178064 KB Output is correct
36 Correct 380 ms 171968 KB Output is correct
37 Correct 441 ms 178188 KB Output is correct
38 Correct 330 ms 172040 KB Output is correct
39 Correct 417 ms 178084 KB Output is correct
40 Correct 485 ms 179040 KB Output is correct
41 Correct 250 ms 158480 KB Output is correct
42 Correct 10 ms 73048 KB Output is correct
43 Correct 446 ms 172628 KB Output is correct
44 Correct 179 ms 148824 KB Output is correct
45 Correct 172 ms 148940 KB Output is correct
46 Correct 157 ms 149812 KB Output is correct
47 Correct 317 ms 186684 KB Output is correct
48 Correct 732 ms 281964 KB Output is correct
49 Correct 495 ms 183892 KB Output is correct
50 Correct 373 ms 175184 KB Output is correct
51 Correct 377 ms 175440 KB Output is correct
52 Correct 136 ms 135496 KB Output is correct
53 Correct 138 ms 135580 KB Output is correct
54 Correct 136 ms 135604 KB Output is correct
55 Correct 740 ms 277312 KB Output is correct
56 Correct 740 ms 281888 KB Output is correct
57 Correct 468 ms 175428 KB Output is correct
58 Correct 672 ms 175564 KB Output is correct

Subtask #7
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 73048 KB Output is correct
2 Correct 11 ms 73052 KB Output is correct
3 Correct 11 ms 73092 KB Output is correct
4 Correct 11 ms 73052 KB Output is correct
5 Correct 12 ms 73048 KB Output is correct
6 Correct 3039 ms 752000 KB Output is correct
7 Correct 3056 ms 747396 KB Output is correct
8 Correct 2195 ms 743600 KB Output is correct
9 Correct 2173 ms 733408 KB Output is correct
10 Correct 3251 ms 707324 KB Output is correct
11 Correct 2703 ms 631004 KB Output is correct
12 Correct 2603 ms 633416 KB Output is correct
13 Correct 2885 ms 689352 KB Output is correct
14 Correct 10 ms 73052 KB Output is correct
15 Correct 2893 ms 749028 KB Output is correct
16 Correct 2884 ms 748668 KB Output is correct
17 Correct 10 ms 73052 KB Output is correct
18 Correct 12 ms 85340 KB Output is correct
19 Correct 11 ms 85404 KB Output is correct
20 Correct 11 ms 85336 KB Output is correct
21 Correct 11 ms 85340 KB Output is correct
22 Correct 12 ms 85336 KB Output is correct
23 Correct 11 ms 85340 KB Output is correct
24 Correct 12 ms 85380 KB Output is correct
25 Correct 11 ms 85348 KB Output is correct
26 Correct 10 ms 73052 KB Output is correct
27 Correct 11 ms 85576 KB Output is correct
28 Correct 12 ms 85596 KB Output is correct
29 Correct 11 ms 85404 KB Output is correct
30 Correct 11 ms 85332 KB Output is correct
31 Correct 16 ms 86876 KB Output is correct
32 Correct 19 ms 86876 KB Output is correct
33 Correct 16 ms 86956 KB Output is correct
34 Correct 17 ms 87132 KB Output is correct
35 Correct 15 ms 86956 KB Output is correct
36 Correct 16 ms 87048 KB Output is correct
37 Correct 17 ms 87132 KB Output is correct
38 Correct 14 ms 86364 KB Output is correct
39 Correct 10 ms 72832 KB Output is correct
40 Correct 18 ms 86876 KB Output is correct
41 Correct 18 ms 87276 KB Output is correct
42 Correct 18 ms 87128 KB Output is correct
43 Correct 17 ms 86876 KB Output is correct
44 Correct 13 ms 86208 KB Output is correct
45 Correct 15 ms 86356 KB Output is correct
46 Correct 14 ms 86108 KB Output is correct
47 Correct 13 ms 86364 KB Output is correct
48 Correct 13 ms 86360 KB Output is correct
49 Correct 14 ms 86360 KB Output is correct
50 Correct 22 ms 89184 KB Output is correct
51 Correct 381 ms 173352 KB Output is correct
52 Correct 415 ms 179288 KB Output is correct
53 Correct 353 ms 172264 KB Output is correct
54 Correct 400 ms 178052 KB Output is correct
55 Correct 334 ms 172216 KB Output is correct
56 Correct 418 ms 177848 KB Output is correct
57 Correct 477 ms 178972 KB Output is correct
58 Correct 259 ms 158488 KB Output is correct
59 Correct 487 ms 179920 KB Output is correct
60 Correct 465 ms 177448 KB Output is correct
61 Correct 364 ms 173436 KB Output is correct
62 Correct 210 ms 151500 KB Output is correct
63 Correct 10 ms 73048 KB Output is correct
64 Correct 9 ms 73052 KB Output is correct
65 Correct 431 ms 172808 KB Output is correct
66 Correct 155 ms 148752 KB Output is correct
67 Correct 171 ms 149956 KB Output is correct
68 Correct 156 ms 150012 KB Output is correct
69 Correct 786 ms 297588 KB Output is correct
70 Correct 379 ms 172088 KB Output is correct
71 Correct 417 ms 178064 KB Output is correct
72 Correct 380 ms 171968 KB Output is correct
73 Correct 441 ms 178188 KB Output is correct
74 Correct 330 ms 172040 KB Output is correct
75 Correct 417 ms 178084 KB Output is correct
76 Correct 485 ms 179040 KB Output is correct
77 Correct 250 ms 158480 KB Output is correct
78 Correct 10 ms 73048 KB Output is correct
79 Correct 446 ms 172628 KB Output is correct
80 Correct 179 ms 148824 KB Output is correct
81 Correct 172 ms 148940 KB Output is correct
82 Correct 157 ms 149812 KB Output is correct
83 Correct 317 ms 186684 KB Output is correct
84 Correct 732 ms 281964 KB Output is correct
85 Correct 495 ms 183892 KB Output is correct
86 Correct 373 ms 175184 KB Output is correct
87 Correct 377 ms 175440 KB Output is correct
88 Correct 136 ms 135496 KB Output is correct
89 Correct 138 ms 135580 KB Output is correct
90 Correct 136 ms 135604 KB Output is correct
91 Correct 740 ms 277312 KB Output is correct
92 Correct 740 ms 281888 KB Output is correct
93 Correct 468 ms 175428 KB Output is correct
94 Correct 672 ms 175564 KB Output is correct
95 Correct 1458 ms 346836 KB Output is correct
96 Correct 1753 ms 365852 KB Output is correct
97 Correct 1455 ms 348068 KB Output is correct
98 Correct 1716 ms 362956 KB Output is correct
99 Correct 1327 ms 346524 KB Output is correct
100 Correct 1541 ms 365616 KB Output is correct
101 Correct 1800 ms 368836 KB Output is correct
102 Correct 963 ms 305244 KB Output is correct
103 Correct 10 ms 73052 KB Output is correct
104 Correct 1442 ms 316364 KB Output is correct
105 Correct 532 ms 275428 KB Output is correct
106 Correct 532 ms 276648 KB Output is correct
107 Correct 545 ms 277724 KB Output is correct
108 Correct 1088 ms 404628 KB Output is correct
109 Correct 2895 ms 688760 KB Output is correct
110 Correct 2033 ms 380996 KB Output is correct
111 Correct 1641 ms 358108 KB Output is correct
112 Correct 1551 ms 357492 KB Output is correct
113 Correct 587 ms 238132 KB Output is correct
114 Correct 530 ms 238028 KB Output is correct
115 Correct 555 ms 238052 KB Output is correct
116 Correct 3159 ms 681332 KB Output is correct
117 Correct 3040 ms 693188 KB Output is correct
118 Correct 1650 ms 358900 KB Output is correct
119 Correct 2427 ms 359692 KB Output is correct