oj.uz

Submission #961394

# Submission time Handle Problem Language Result Execution time Memory
961394 2024-04-12T03:34:52 Z Nhoksocqt1 Swapping Cities (APIO20_swap) C++17
73 / 100
 2000 ms 97744 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

class DisjointSet {
    private:
        vector<int> lab;

    public:
        DisjointSet(int _n = 0) {
            lab.assign(_n + 7, -1);
        }

        int find(int u) {
            return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
        }

        bool join(int u, int v) {
            u = find(u), v = find(v);
            if(u == v)
                return (false);

            if(lab[u] > lab[v])
                swap(u, v);

            lab[u] += lab[v];
            lab[v] = u;
            return (true);
        }

        int getSize(int u) {
            return -lab[find(u)];
        }

} dsu;

struct Edge {
    int u, v, w;
} edge[2 * MAXN];

struct SegNode {
    int cnt, L, R;
} seg[50 * MAXN];

vector<int> idw;
vector<ii> adj[MAXN];
int version[MAXN], tIn[MAXN], tOut[MAXN], tour[MAXN], depth[MAXN], P[MAXN][17], Pw[MAXN][17];
int deg[MAXN], pa[MAXN], cntLeaf[MAXN], tmp[MAXN], cntChild[MAXN], maxw, nTree, numNode, numEdge;
bool dp[1003][1003], dx[MAXN], check_sub1, check_sub2;

int cntTime(0);
void preDfs(int u) {
    tIn[u] = ++cntTime;
    tour[cntTime] = u;

    ++tmp[tIn[u]];
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), id(adj[u][it].se);
        if(v != P[u][0]) {
            depth[v] = depth[u] + 1;
            P[v][0] = u;
            Pw[v][0] = id;
            preDfs(v);
            --tmp[tIn[u]];
        }
    }

    tOut[u] = cntTime;
}

int lca(int u, int v) {
    if(depth[u] < depth[v])
        swap(u, v);

    for (int i1 = depth[u] - depth[v]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        u = P[u][i];
    }

    if(u == v)
        return u;

    for (int i = 31 - __builtin_clz(depth[u]); i >= 0; --i) {
        if(P[u][i] != P[v][i])
            u = P[u][i], v = P[v][i];
    }

    return P[u][0];
}

int build(int l, int r, int tmp[]) {
    if(l == r) {
        seg[++nTree].cnt = tmp[l];
        return nTree;
    }

    int cur(++nTree), mid = (l + r) >> 1;
    seg[cur].L = build(l, mid, tmp);
    seg[cur].R = build(mid + 1, r, tmp);

    seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt;
    return cur;
}

int update(int oldID, int l, int r, int pos, int val) {
    if(l == r) {
        seg[++nTree] = seg[oldID];
        seg[nTree].cnt += val;
        return nTree;
    }

    int cur(++nTree), mid = (l + r) >> 1;
    seg[cur] = seg[oldID];

    if(pos <= mid) {
        seg[cur].L = update(seg[oldID].L, l, mid, pos, val);
    } else {
        seg[cur].R = update(seg[oldID].R, mid + 1, r, pos, val);
    }

    seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt;
    return cur;
}

int query(int id, int l, int r, int u, int v) {
    if(u <= l && r <= v)
        return seg[id].cnt;

    int mid = (l + r) >> 1, res(0);
    if(mid >= u)
        res += query(seg[id].L, l, mid, u, v);

    if(mid + 1 <= v)
        res += query(seg[id].R, mid + 1, r, u, v);

    return res;
}

void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W) {
    numNode = _N, numEdge = _M;

    for (int i = 0; i < numEdge; ++i) {
        edge[i] = {_U[i], _V[i], _W[i]};
        maxw = max(maxw, edge[i].w);
        ++deg[edge[i].u], ++deg[edge[i].v];
    }

    check_sub1 = 1;
    for (int i = 0; i < numNode; ++i)
        check_sub1 &= (deg[i] <= 2);

    sort(edge, edge + numEdge, [](const Edge &a, const Edge &b) {
        return (a.w < b.w);
    });

    dsu = DisjointSet(numNode);

    int cnt(0);
    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].u), v(edge[i].v);
        if(dsu.join(u, v)) {
            adj[u].push_back(ii(v, cnt));
            adj[v].push_back(ii(u, cnt));
            idw.push_back(edge[i].w);
            ++cnt;
        }
    }

    P[0][0] = -1, depth[0] = 1;
    preDfs(0);

    for (int j = 1; (1 << j) <= numNode; ++j) {
        for (int i = 0; i < numNode; ++i) {
            if(P[i][j - 1] == -1) {
                P[i][j] = -1;
            } else {
                P[i][j] = P[P[i][j - 1]][j - 1];
                Pw[i][j] = max(Pw[i][j - 1], Pw[P[i][j - 1]][j - 1]);
            }
        }
    }

    version[0] = build(1, numNode, tmp);

    cnt = 0;
    dsu = DisjointSet(numNode);
    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].u), v(edge[i].v);
        if(dsu.find(u) != dsu.find(v)) {
            if(P[u][0] == v)
                swap(u, v);

            ++cnt;
            int qr = query(version[cnt - 1], 1, numNode, tIn[v], tOut[v]) - (++cntChild[u] == 2);
            version[cnt] = update(version[cnt - 1], 1, numNode, tIn[u], qr);
            if(++cntChild[v] == 2) {
                version[cnt] = update(version[cnt], 1, numNode, tIn[v], -1);
                --qr;
            }

            int w(u);
            for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) {
                if(P[w][i] != -1 && dsu.find(P[w][i]) == dsu.find(u))
                    w = P[w][i];
            }

            w = P[w][0];
            if(w != -1)
                version[cnt] = update(version[cnt], 1, numNode, tIn[w], -qr);

            dsu.join(u, v);
            //cerr << cnt << ' ' << nTree << '\n';
            /*cout << u << ' ' << v << ": ";
            for (int i = 0; i < numNode; ++i)
                cout << query(version[cnt], 1, numNode, tIn[i], tOut[i]) << ' '; cout << '\n';*/
        }
    }
}

ii dfs(int u) {
    dx[u] = 1;
    cntLeaf[u] = 0;
    ii res = {sz(adj[u]), 1};
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi);
        if(!dx[v]) {
            pa[v] = u;
            ii tmp = dfs(v);
            res = {res.fi + tmp.fi, res.se + tmp.se};
            cntLeaf[u] += cntLeaf[v];
        }
    }

    if(cntLeaf[u] == 0)
        cntLeaf[u] = 1;

    return res;
}

int brute(int x, int y) {
    int l(0), r(numEdge - 1), ans(-1);
    while(l <= r) {
        int mid = (l + r) >> 1;

        for (int i = 0; i < numNode; ++i) {
            adj[i].clear();
            dx[i] = 0;
        }

        for (int i = 0; i <= mid; ++i) {
            int u(edge[i].u), v(edge[i].v);
            adj[u].push_back(ii(v, 0));
            adj[v].push_back(ii(u, 0));
        }

        pa[x] = -1;
        ii res = dfs(x);
        bool check(0);
        if(dx[y]) {
            int u(y);
            while(pa[u] != x)
                u = pa[u];

            check = (res.fi / 2 >= res.se || cntLeaf[y] > 1 || cntLeaf[x] - cntLeaf[u] > 1 || cntLeaf[u] - cntLeaf[y] > 0);
        }

        if(check) {
            ans = edge[mid].w;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

int sub5(int x, int y) {
    int l(0), r(numNode - 1), ans(-1);
    int par = lca(x, y);

    int tmp(x);
    for (int i1 = depth[x] - depth[par]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        l = max(l, Pw[tmp][i]);
        tmp = P[tmp][i];
    }

    tmp = y;
    for (int i1 = depth[y] - depth[par]; i1 > 0; i1 ^= i1 & -i1) {
        int i = __builtin_ctz(i1);
        l = max(l, Pw[tmp][i]);
        tmp = P[tmp][i];
    }

    if(par == y)
        swap(x, y);

    int c(-1);
    if(par == x) {
        c = y;
        for (int i1 = depth[y] - depth[x] - 1; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1);
            c = P[c][i];
        }
    }

    while(l <= r) {
        int mid = (l + r) >> 1;

        bool check(0);
        if(par == x) {
            int w(x);
            for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) {
                if(P[w][i] != -1 && Pw[w][i] <= mid)
                    w = P[w][i];
            }

            int cntLeafc = query(version[mid + 1], 1, numNode, tIn[c], tOut[c]);
            int cntLeafx = query(version[mid + 1], 1, numNode, tIn[w], tOut[w]) - cntLeafc;
            int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
            int cntLeafInPath = cntLeafc - cntLeafy;

            //cout << idw[mid] << ' ' << cntLeafc << ' ' << cntLeafx << ' ' << cntLeafy << ' ' << cntLeafInPath << '\n';
            check = (cntLeafx > 1 || cntLeafy > 1 || cntLeafInPath > 0);
        } else {
            if(par > 0 && Pw[par][0] <= mid) {
                check = 1;
            } else {
                int cntLeafx = query(version[mid + 1], 1, numNode, tIn[x], tOut[x]);
                int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]);
                int cntLeafInPath = query(version[mid + 1], 1, numNode, tIn[par], tOut[par]) - cntLeafx - cntLeafy;
                check = (cntLeafx > 1 || cntLeafy > 1 || cntLeafInPath > 0);
            }
        }

        if(check) {
            ans = idw[mid];
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

int getMinimumFuelCapacity(int x, int y) {
    /*cout << sub5(x, y) << ' ' << brute(x, y) << '\n';
    if(sub5(x, y) != brute(x, y))
        exit(1);*/

    if(check_sub1)
        return (numNode == numEdge) ? maxw : -1;

    if(numEdge == numNode - 1)
        return sub5(x, y);

    return brute(x, y);
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "swap"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _U, _V, _W;
    int _N, _M, _Q;
    cin >> _N >> _M >> _Q;
    //_N = Random(5e1, 1e2), _M = Random(_N - 1, _N - 1), _Q = Random(5e4, 2e5); cout << _N << ' ' << _M << ' ' << _Q << '\n';

    _U.resize(_M), _V.resize(_M), _W.resize(_M);
    for (int i = 0; i < _M; ++i) {
        cin >> _U[i] >> _V[i] >> _W[i];
        //_U[i] = Random(max(0, i - 10), i), _V[i] = i + 1, _W[i] = Random(1, 1e5); cout << _U[i] << ' ' << _V[i] << ' ' << _W[i] << '\n';
    }

    init(_N, _M, _U, _V, _W);
    for (int t = 0; t < _Q; ++t) {
        int _X, _Y;
        cin >> _X >> _Y;
        //_X = Random(0, _N - 2), _Y = Random(_X + 1, _N - 1);
        cout << "MINIMUM FUEL CAPACITY " << _X << " TO " << _Y << ": " << getMinimumFuelCapacity(_X, _Y) << '\n';
        if(t % 100 == 0)
            cerr << "RUNNING ON QUERY " << t << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 4 ms 16852 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16872 KB Output is correct
9 Correct 169 ms 75684 KB Output is correct
10 Correct 207 ms 89424 KB Output is correct
11 Correct 208 ms 86728 KB Output is correct
12 Correct 241 ms 91892 KB Output is correct
13 Correct 135 ms 72776 KB Output is correct
14 Correct 180 ms 75572 KB Output is correct
15 Correct 262 ms 93264 KB Output is correct
16 Correct 252 ms 89632 KB Output is correct
17 Correct 293 ms 97188 KB Output is correct
18 Correct 199 ms 83844 KB Output is correct
19 Correct 58 ms 32476 KB Output is correct
20 Correct 293 ms 93804 KB Output is correct
21 Correct 238 ms 90952 KB Output is correct
22 Correct 273 ms 96908 KB Output is correct
23 Correct 198 ms 87068 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 769 ms 59392 KB Output is correct
4 Correct 698 ms 61612 KB Output is correct
5 Correct 772 ms 59652 KB Output is correct
6 Correct 710 ms 61592 KB Output is correct
7 Correct 789 ms 61872 KB Output is correct
8 Correct 743 ms 59284 KB Output is correct
9 Correct 762 ms 61572 KB Output is correct
10 Correct 742 ms 59408 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 4 ms 16852 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16872 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 4 ms 16856 KB Output is correct
11 Correct 5 ms 16732 KB Output is correct
12 Correct 3 ms 16728 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16984 KB Output is correct
15 Correct 3 ms 16728 KB Output is correct
16 Correct 4 ms 16732 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 4 ms 16732 KB Output is correct
22 Correct 4 ms 16732 KB Output is correct
23 Correct 4 ms 16732 KB Output is correct
24 Correct 5 ms 16988 KB Output is correct
25 Correct 5 ms 16988 KB Output is correct
26 Correct 4 ms 16988 KB Output is correct
27 Correct 4 ms 16892 KB Output is correct
28 Correct 5 ms 16984 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 4 ms 16852 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 4 ms 16872 KB Output is correct
10 Correct 169 ms 75684 KB Output is correct
11 Correct 207 ms 89424 KB Output is correct
12 Correct 208 ms 86728 KB Output is correct
13 Correct 241 ms 91892 KB Output is correct
14 Correct 135 ms 72776 KB Output is correct
15 Correct 4 ms 16856 KB Output is correct
16 Correct 5 ms 16732 KB Output is correct
17 Correct 3 ms 16728 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16984 KB Output is correct
20 Correct 3 ms 16728 KB Output is correct
21 Correct 4 ms 16732 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 4 ms 16732 KB Output is correct
25 Correct 5 ms 16988 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 4 ms 16732 KB Output is correct
29 Correct 5 ms 16988 KB Output is correct
30 Correct 5 ms 16988 KB Output is correct
31 Correct 4 ms 16988 KB Output is correct
32 Correct 4 ms 16892 KB Output is correct
33 Correct 5 ms 16984 KB Output is correct
34 Correct 19 ms 24156 KB Output is correct
35 Correct 232 ms 91172 KB Output is correct
36 Correct 239 ms 88900 KB Output is correct
37 Correct 241 ms 87616 KB Output is correct
38 Correct 224 ms 85340 KB Output is correct
39 Correct 229 ms 84752 KB Output is correct
40 Correct 161 ms 77828 KB Output is correct
41 Correct 237 ms 90116 KB Output is correct
42 Correct 227 ms 90624 KB Output is correct
43 Correct 143 ms 83276 KB Output is correct
44 Correct 190 ms 81472 KB Output is correct
45 Correct 435 ms 70828 KB Output is correct
46 Correct 445 ms 91072 KB Output is correct
47 Correct 478 ms 86960 KB Output is correct
48 Correct 486 ms 79356 KB Output is correct
49 Correct 68 ms 24888 KB Output is correct
50 Correct 86 ms 25788 KB Output is correct
51 Correct 298 ms 60952 KB Output is correct
52 Correct 539 ms 97744 KB Output is correct
53 Correct 422 ms 86568 KB Output is correct
54 Correct 482 ms 95612 KB Output is correct
55 Correct 352 ms 80560 KB Output is correct
56 Correct 630 ms 81996 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 4 ms 16852 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16872 KB Output is correct
9 Correct 169 ms 75684 KB Output is correct
10 Correct 207 ms 89424 KB Output is correct
11 Correct 208 ms 86728 KB Output is correct
12 Correct 241 ms 91892 KB Output is correct
13 Correct 135 ms 72776 KB Output is correct
14 Correct 180 ms 75572 KB Output is correct
15 Correct 262 ms 93264 KB Output is correct
16 Correct 252 ms 89632 KB Output is correct
17 Correct 293 ms 97188 KB Output is correct
18 Correct 199 ms 83844 KB Output is correct
19 Correct 769 ms 59392 KB Output is correct
20 Correct 698 ms 61612 KB Output is correct
21 Correct 772 ms 59652 KB Output is correct
22 Correct 710 ms 61592 KB Output is correct
23 Correct 789 ms 61872 KB Output is correct
24 Correct 743 ms 59284 KB Output is correct
25 Correct 762 ms 61572 KB Output is correct
26 Correct 742 ms 59408 KB Output is correct
27 Correct 4 ms 16856 KB Output is correct
28 Correct 5 ms 16732 KB Output is correct
29 Correct 3 ms 16728 KB Output is correct
30 Correct 3 ms 16732 KB Output is correct
31 Correct 3 ms 16984 KB Output is correct
32 Correct 3 ms 16728 KB Output is correct
33 Correct 4 ms 16732 KB Output is correct
34 Correct 3 ms 16988 KB Output is correct
35 Correct 3 ms 16988 KB Output is correct
36 Correct 19 ms 24156 KB Output is correct
37 Correct 232 ms 91172 KB Output is correct
38 Correct 239 ms 88900 KB Output is correct
39 Correct 241 ms 87616 KB Output is correct
40 Correct 224 ms 85340 KB Output is correct
41 Correct 229 ms 84752 KB Output is correct
42 Correct 161 ms 77828 KB Output is correct
43 Correct 237 ms 90116 KB Output is correct
44 Correct 227 ms 90624 KB Output is correct
45 Correct 143 ms 83276 KB Output is correct
46 Correct 190 ms 81472 KB Output is correct
47 Correct 32 ms 24656 KB Output is correct
48 Correct 711 ms 94472 KB Output is correct
49 Correct 603 ms 93392 KB Output is correct
50 Correct 611 ms 92588 KB Output is correct
51 Correct 419 ms 92048 KB Output is correct
52 Correct 396 ms 87152 KB Output is correct
53 Correct 244 ms 67632 KB Output is correct
54 Correct 756 ms 94668 KB Output is correct
55 Correct 648 ms 94856 KB Output is correct
56 Correct 1715 ms 93040 KB Output is correct
57 Correct 347 ms 88892 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 4 ms 16852 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 4 ms 16872 KB Output is correct
10 Correct 169 ms 75684 KB Output is correct
11 Correct 207 ms 89424 KB Output is correct
12 Correct 208 ms 86728 KB Output is correct
13 Correct 241 ms 91892 KB Output is correct
14 Correct 135 ms 72776 KB Output is correct
15 Correct 180 ms 75572 KB Output is correct
16 Correct 262 ms 93264 KB Output is correct
17 Correct 252 ms 89632 KB Output is correct
18 Correct 293 ms 97188 KB Output is correct
19 Correct 199 ms 83844 KB Output is correct
20 Correct 769 ms 59392 KB Output is correct
21 Correct 698 ms 61612 KB Output is correct
22 Correct 772 ms 59652 KB Output is correct
23 Correct 710 ms 61592 KB Output is correct
24 Correct 789 ms 61872 KB Output is correct
25 Correct 743 ms 59284 KB Output is correct
26 Correct 762 ms 61572 KB Output is correct
27 Correct 742 ms 59408 KB Output is correct
28 Correct 4 ms 16856 KB Output is correct
29 Correct 5 ms 16732 KB Output is correct
30 Correct 3 ms 16728 KB Output is correct
31 Correct 3 ms 16732 KB Output is correct
32 Correct 3 ms 16984 KB Output is correct
33 Correct 3 ms 16728 KB Output is correct
34 Correct 4 ms 16732 KB Output is correct
35 Correct 3 ms 16988 KB Output is correct
36 Correct 3 ms 16988 KB Output is correct
37 Correct 19 ms 24156 KB Output is correct
38 Correct 232 ms 91172 KB Output is correct
39 Correct 239 ms 88900 KB Output is correct
40 Correct 241 ms 87616 KB Output is correct
41 Correct 224 ms 85340 KB Output is correct
42 Correct 229 ms 84752 KB Output is correct
43 Correct 161 ms 77828 KB Output is correct
44 Correct 237 ms 90116 KB Output is correct
45 Correct 227 ms 90624 KB Output is correct
46 Correct 143 ms 83276 KB Output is correct
47 Correct 190 ms 81472 KB Output is correct
48 Correct 32 ms 24656 KB Output is correct
49 Correct 711 ms 94472 KB Output is correct
50 Correct 603 ms 93392 KB Output is correct
51 Correct 611 ms 92588 KB Output is correct
52 Correct 419 ms 92048 KB Output is correct
53 Correct 396 ms 87152 KB Output is correct
54 Correct 244 ms 67632 KB Output is correct
55 Correct 756 ms 94668 KB Output is correct
56 Correct 648 ms 94856 KB Output is correct
57 Correct 1715 ms 93040 KB Output is correct
58 Correct 347 ms 88892 KB Output is correct
59 Correct 58 ms 32476 KB Output is correct
60 Correct 293 ms 93804 KB Output is correct
61 Correct 238 ms 90952 KB Output is correct
62 Correct 273 ms 96908 KB Output is correct
63 Correct 198 ms 87068 KB Output is correct
64 Correct 4 ms 16732 KB Output is correct
65 Correct 5 ms 16988 KB Output is correct
66 Correct 4 ms 16732 KB Output is correct
67 Correct 4 ms 16732 KB Output is correct
68 Correct 4 ms 16732 KB Output is correct
69 Correct 5 ms 16988 KB Output is correct
70 Correct 5 ms 16988 KB Output is correct
71 Correct 4 ms 16988 KB Output is correct
72 Correct 4 ms 16892 KB Output is correct
73 Correct 5 ms 16984 KB Output is correct
74 Correct 435 ms 70828 KB Output is correct
75 Correct 445 ms 91072 KB Output is correct
76 Correct 478 ms 86960 KB Output is correct
77 Correct 486 ms 79356 KB Output is correct
78 Correct 68 ms 24888 KB Output is correct
79 Correct 86 ms 25788 KB Output is correct
80 Correct 298 ms 60952 KB Output is correct
81 Correct 539 ms 97744 KB Output is correct
82 Correct 422 ms 86568 KB Output is correct
83 Correct 482 ms 95612 KB Output is correct
84 Correct 352 ms 80560 KB Output is correct
85 Correct 630 ms 81996 KB Output is correct
86 Execution timed out 2013 ms 39156 KB Time limit exceeded
87 Halted 0 ms 0 KB -