oj.uz

Submission #439990

# Submission time Handle Problem Language Result Execution time Memory
439990 2021-07-01T10:57:31 Z cheeheng Fountain Parks (IOI21_parks) C++17
70 / 100
 3500 ms 627116 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

const int dx[] = {-1,0,0,1};
const int dy[] = {0,1,-1,0};

vector<int> AdjList[200005];
ii EdgeList[800005];
ii EdgeList2[800005];
map<ii, int> indx;
map<ii, int> indx2;
map<ii, int> indxEdge;
map<ii, int> indxBench;

vector<int> AdjListBench[800005];
vector<int> AdjListRoad[200005];
int degBench[800005];
ii benchXY[800005];

mt19937 rng(1);

struct Dinic{
    static const int MAX_E = 1000005;
    static const int MAX_V = 1000005;

    // Edge List
    ii EdgeList[MAX_E<<1];
    int flow[MAX_E<<1];
    int capacity[MAX_E<<1];

    vector<int> AdjList[MAX_V];
    int level[MAX_V];
    int ptr[MAX_V];

    int E = 0;

    int s, t;

    Dinic(int _s, int _t){
        s = _s;
        t = _t;
    }

    void add_edge(int u, int v, int c){
        EdgeList[E] = ii(u, v);
        EdgeList[E+1] = ii(v, u);
        flow[E] = 0;
        flow[E+1] = 0;
        capacity[E] = c;
        capacity[E+1] = 0;

        AdjList[u].push_back(E);
        AdjList[v].push_back(E+1);

        E += 2;
    }

    bool bfs(){
        memset(level, -1, sizeof(level));
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int indx: AdjList[u]){
                int v = EdgeList[indx].second;
                if(level[v] == -1 && capacity[indx] > flow[indx]){
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int flowToSend){
        if(u == t){return flowToSend;}
        if(flowToSend == 0){return 0;}

        while(ptr[u] < (int)AdjList[u].size()){
            int indx = AdjList[u][ptr[u]];
            int v = EdgeList[indx].second;
            if(capacity[indx] > flow[indx] && level[v] == level[u] + 1){
                int nxtFlow = min(flowToSend, capacity[indx] - flow[indx]);
                int flowSent = dfs(v, nxtFlow);
                if(flowSent > 0){
                    flow[indx] += flowSent; // flow from u to v
                    flow[indx^1] -= flowSent; // flow from v to u
                    return flowSent;
                }
            }
            ptr[u] ++;
        }
        return 0;
    }

    int findMaxFlow(){
        int maxFlow = 0;
        while(1){
            if(!bfs()){return maxFlow;}

            memset(ptr, 0, sizeof(ptr));
            while(1){
                int temp = dfs(s, INT_MAX);
                maxFlow += temp;
                if(temp == 0){break;}
            }
        }
    }
};

struct UnionFind{
    vector<int> p;
    vector<int> rank1;
    void init(int n){
        p.assign(n, 0);
        rank1.assign(n, 0);
        for(int i = 0; i < n; i ++){
            p[i] = i;
            rank1[i] = 0;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    void unionSet(int i, int j){
        int x = findSet(i);
        int y = findSet(j);

        if(x != y){
            if(rank1[x] > rank1[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank1[x] == rank1[y]){
                    rank1[y] ++;
                }
            }
        }
    }
};

int p[200005];

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = (int)x.size();
    if (n == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    vector<int> U(n-1);
    vector<int> V(n-1);
    vector<int> A(n-1);
    vector<int> B(n-1);

    for(int i = 0; i < n; i ++){
        indx[ii(x[i], y[i])] = i;
    }

    for(int i = 0; i < n; i ++){
        indx2[ii(y[i], x[i])] = i;
    }

    int cnt3 = 0;
    for(pair<ii, int> temp: indx2){
        p[cnt3 ++] = temp.second;
    }

    int m = 0;
    for(int i = 0; i < n; i ++){
        int i2 = p[i];
        for(int k: {0, 3}){
            int nx = x[i2] + 2*dx[k];
            int ny = y[i2] + 2*dy[k];

            if(indx.find(ii(nx, ny)) != indx.end()){
                int j = indx[ii(nx, ny)];
                EdgeList[m ++] = ii(i2, j);
            }
        }
    }

    for(int i = 0; i < n; i ++){
        int i2 = p[i];
        for(int k: {2, 1}){
            int nx = x[i2] + 2*dx[k];
            int ny = y[i2] + 2*dy[k];

            if(indx.find(ii(nx, ny)) != indx.end()){
                int j = indx[ii(nx, ny)];
                EdgeList[m ++] = ii(i2, j);
            }
        }
    }

    UnionFind* uf = new UnionFind();
    while(1){
        uf->init(n);

        for(int i = 0; i < n; i ++){
            AdjList[i] = vector<int>();
            //AdjListRoad[i] = set<int>();
        }

        for(int i = 0; i < 4*n; i ++){
            //AdjListBench[i] = vector<int>();
        }

        int cnt = 0;
        for(int i = 0; i < m; i ++){
            int u, v;
            tie(u, v) = EdgeList[i];
            if(!uf->isSameSet(u, v)){
                uf->unionSet(u, v);
                AdjList[u].push_back(v);
                AdjList[v].push_back(u);
                EdgeList2[cnt] = ii(u, v);
                indxEdge[ii(u, v)] = cnt;
                cnt ++;
            }
        }

        if(cnt != n-1){
            return 0;
        }

        int benches = 0;
        memset(degBench, 0, sizeof(degBench));
        for(int i = 0; i < n-1; i ++){
            int u, v;
            tie(u, v) = EdgeList2[i];
            int x2 = (x[u] + x[v])/2;
            int y2 = (y[u] + y[v])/2;

            for(int k = 0; k < 4; k ++){
                int nx = x2 + dx[k];
                int ny = y2 + dy[k];
                if(nx%2 == 1 && ny%2 == 1){
                    int indx2 = benches;
                    if(indxBench.find(ii(nx, ny)) != indxBench.end()){
                        indx2 = indxBench[ii(nx, ny)];
                    }else{
                        benchXY[benches] = ii(nx, ny);
                        indxBench[ii(nx, ny)] = benches;
                        //printf("bench %d; (%d, %d)\n", benches, nx, ny);
                        benches ++;
                    }

                    //AdjListBench[indx2].push_back(i);
                    AdjListRoad[i].push_back(indx2);
                    //printf("road %d; bench %d\n", i, indx2);
                    degBench[i] ++;
                }
            }
        }

        int S = n+benches;
        int T = n+benches+1;
        Dinic* mf = new Dinic(S, T);

        for(int i = 0; i < n; i ++){
            mf->add_edge(S, i, 1);
        }

        for(int i = 0; i < benches; i ++){
            mf->add_edge(n+i, T, 1);
        }

        for(int i = 0; i < n; i ++){
            for(int j: AdjListRoad[i]){
                mf->add_edge(i, n+j, 1);
            }
        }

        int res = mf->findMaxFlow();
        //printf("res=%d\n", res);
        if(res != n-1){
            shuffle(EdgeList, EdgeList+m, rng);
            continue;
        }

        int cnt2 = 0;
        for(int i = 0; i < mf->E; i ++){
            int u, v;
            tie(u, v) = mf->EdgeList[i];
            //printf("u=%d v=%d\n", u, v);
            if(u >= n){continue;}

            if(mf->flow[i] > 0){
                tie(U[cnt2], V[cnt2]) = EdgeList2[u];
                tie(A[cnt2], B[cnt2]) = benchXY[v-n];
                cnt2 ++;
            }
        }

        if(cnt2 == n-1){
            build(U, V, A, B);
            return 1;
        }
        shuffle(EdgeList, EdgeList+m, rng);
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28492 KB Output is correct
2 Correct 46 ms 78532 KB Output is correct
3 Correct 17 ms 28484 KB Output is correct
4 Correct 45 ms 78512 KB Output is correct
5 Correct 45 ms 78548 KB Output is correct
6 Correct 17 ms 28460 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 19 ms 28492 KB Output is correct
9 Correct 554 ms 145976 KB Output is correct
10 Correct 73 ms 85508 KB Output is correct
11 Correct 262 ms 115192 KB Output is correct
12 Correct 93 ms 89028 KB Output is correct
13 Correct 90 ms 41132 KB Output is correct
14 Correct 20 ms 28716 KB Output is correct
15 Correct 26 ms 28996 KB Output is correct
16 Correct 533 ms 145848 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28492 KB Output is correct
2 Correct 46 ms 78532 KB Output is correct
3 Correct 17 ms 28484 KB Output is correct
4 Correct 45 ms 78512 KB Output is correct
5 Correct 45 ms 78548 KB Output is correct
6 Correct 17 ms 28460 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 19 ms 28492 KB Output is correct
9 Correct 554 ms 145976 KB Output is correct
10 Correct 73 ms 85508 KB Output is correct
11 Correct 262 ms 115192 KB Output is correct
12 Correct 93 ms 89028 KB Output is correct
13 Correct 90 ms 41132 KB Output is correct
14 Correct 20 ms 28716 KB Output is correct
15 Correct 26 ms 28996 KB Output is correct
16 Correct 533 ms 145848 KB Output is correct
17 Correct 43 ms 78508 KB Output is correct
18 Correct 43 ms 78552 KB Output is correct
19 Correct 44 ms 78532 KB Output is correct
20 Correct 44 ms 78564 KB Output is correct
21 Correct 17 ms 28424 KB Output is correct
22 Correct 44 ms 78584 KB Output is correct
23 Correct 1304 ms 190556 KB Output is correct
24 Correct 47 ms 78532 KB Output is correct
25 Correct 45 ms 79268 KB Output is correct
26 Correct 24 ms 29324 KB Output is correct
27 Correct 27 ms 29620 KB Output is correct
28 Correct 414 ms 123492 KB Output is correct
29 Correct 653 ms 145808 KB Output is correct
30 Correct 946 ms 168408 KB Output is correct
31 Correct 1293 ms 190668 KB Output is correct
32 Correct 47 ms 78532 KB Output is correct
33 Correct 45 ms 78668 KB Output is correct
34 Correct 44 ms 78608 KB Output is correct
35 Correct 18 ms 28420 KB Output is correct
36 Correct 18 ms 28384 KB Output is correct
37 Correct 43 ms 78540 KB Output is correct
38 Correct 42 ms 78544 KB Output is correct
39 Correct 41 ms 78584 KB Output is correct
40 Correct 52 ms 78528 KB Output is correct
41 Correct 18 ms 28492 KB Output is correct
42 Correct 45 ms 78592 KB Output is correct
43 Correct 21 ms 29004 KB Output is correct
44 Correct 22 ms 29268 KB Output is correct
45 Correct 570 ms 138312 KB Output is correct
46 Correct 872 ms 165552 KB Output is correct
47 Correct 864 ms 165688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28492 KB Output is correct
2 Correct 46 ms 78532 KB Output is correct
3 Correct 17 ms 28484 KB Output is correct
4 Correct 45 ms 78512 KB Output is correct
5 Correct 45 ms 78548 KB Output is correct
6 Correct 17 ms 28460 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 19 ms 28492 KB Output is correct
9 Correct 554 ms 145976 KB Output is correct
10 Correct 73 ms 85508 KB Output is correct
11 Correct 262 ms 115192 KB Output is correct
12 Correct 93 ms 89028 KB Output is correct
13 Correct 90 ms 41132 KB Output is correct
14 Correct 20 ms 28716 KB Output is correct
15 Correct 26 ms 28996 KB Output is correct
16 Correct 533 ms 145848 KB Output is correct
17 Correct 43 ms 78508 KB Output is correct
18 Correct 43 ms 78552 KB Output is correct
19 Correct 44 ms 78532 KB Output is correct
20 Correct 44 ms 78564 KB Output is correct
21 Correct 17 ms 28424 KB Output is correct
22 Correct 44 ms 78584 KB Output is correct
23 Correct 1304 ms 190556 KB Output is correct
24 Correct 47 ms 78532 KB Output is correct
25 Correct 45 ms 79268 KB Output is correct
26 Correct 24 ms 29324 KB Output is correct
27 Correct 27 ms 29620 KB Output is correct
28 Correct 414 ms 123492 KB Output is correct
29 Correct 653 ms 145808 KB Output is correct
30 Correct 946 ms 168408 KB Output is correct
31 Correct 1293 ms 190668 KB Output is correct
32 Correct 47 ms 78532 KB Output is correct
33 Correct 45 ms 78668 KB Output is correct
34 Correct 44 ms 78608 KB Output is correct
35 Correct 18 ms 28420 KB Output is correct
36 Correct 18 ms 28384 KB Output is correct
37 Correct 43 ms 78540 KB Output is correct
38 Correct 42 ms 78544 KB Output is correct
39 Correct 41 ms 78584 KB Output is correct
40 Correct 52 ms 78528 KB Output is correct
41 Correct 18 ms 28492 KB Output is correct
42 Correct 45 ms 78592 KB Output is correct
43 Correct 21 ms 29004 KB Output is correct
44 Correct 22 ms 29268 KB Output is correct
45 Correct 570 ms 138312 KB Output is correct
46 Correct 872 ms 165552 KB Output is correct
47 Correct 864 ms 165688 KB Output is correct
48 Correct 44 ms 78600 KB Output is correct
49 Correct 45 ms 78612 KB Output is correct
50 Correct 45 ms 78600 KB Output is correct
51 Correct 46 ms 78532 KB Output is correct
52 Correct 44 ms 78536 KB Output is correct
53 Correct 46 ms 78532 KB Output is correct
54 Correct 45 ms 78572 KB Output is correct
55 Correct 1297 ms 191240 KB Output is correct
56 Correct 44 ms 78588 KB Output is correct
57 Correct 50 ms 79688 KB Output is correct
58 Correct 64 ms 82112 KB Output is correct
59 Correct 43 ms 31452 KB Output is correct
60 Correct 560 ms 137688 KB Output is correct
61 Correct 775 ms 155108 KB Output is correct
62 Correct 969 ms 171576 KB Output is correct
63 Correct 1363 ms 191192 KB Output is correct
64 Correct 19 ms 28492 KB Output is correct
65 Correct 45 ms 78568 KB Output is correct
66 Correct 19 ms 28404 KB Output is correct
67 Correct 1296 ms 213276 KB Output is correct
68 Correct 1195 ms 213368 KB Output is correct
69 Correct 1221 ms 212628 KB Output is correct
70 Correct 25 ms 29516 KB Output is correct
71 Correct 34 ms 30744 KB Output is correct
72 Correct 558 ms 138196 KB Output is correct
73 Correct 919 ms 168276 KB Output is correct
74 Correct 1225 ms 197860 KB Output is correct
75 Correct 1344 ms 199356 KB Output is correct
76 Correct 1298 ms 213424 KB Output is correct
77 Correct 28 ms 29832 KB Output is correct
78 Correct 41 ms 31064 KB Output is correct
79 Correct 584 ms 138204 KB Output is correct
80 Correct 913 ms 168308 KB Output is correct
81 Correct 1310 ms 197932 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28492 KB Output is correct
2 Correct 46 ms 78532 KB Output is correct
3 Correct 17 ms 28484 KB Output is correct
4 Correct 45 ms 78512 KB Output is correct
5 Correct 45 ms 78548 KB Output is correct
6 Correct 17 ms 28460 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 19 ms 28492 KB Output is correct
9 Correct 554 ms 145976 KB Output is correct
10 Correct 73 ms 85508 KB Output is correct
11 Correct 262 ms 115192 KB Output is correct
12 Correct 93 ms 89028 KB Output is correct
13 Correct 90 ms 41132 KB Output is correct
14 Correct 20 ms 28716 KB Output is correct
15 Correct 26 ms 28996 KB Output is correct
16 Correct 533 ms 145848 KB Output is correct
17 Correct 44 ms 78544 KB Output is correct
18 Correct 43 ms 78568 KB Output is correct
19 Correct 18 ms 28500 KB Output is correct
20 Correct 1264 ms 190152 KB Output is correct
21 Correct 1236 ms 190264 KB Output is correct
22 Correct 1340 ms 190192 KB Output is correct
23 Correct 1113 ms 193160 KB Output is correct
24 Correct 643 ms 62132 KB Output is correct
25 Correct 1205 ms 85708 KB Output is correct
26 Correct 1197 ms 85684 KB Output is correct
27 Correct 1576 ms 213180 KB Output is correct
28 Correct 1515 ms 213168 KB Output is correct
29 Correct 1640 ms 213172 KB Output is correct
30 Correct 1575 ms 213092 KB Output is correct
31 Correct 52 ms 78532 KB Output is correct
32 Correct 114 ms 87168 KB Output is correct
33 Correct 235 ms 45348 KB Output is correct
34 Correct 1443 ms 190344 KB Output is correct
35 Correct 53 ms 31240 KB Output is correct
36 Correct 172 ms 42852 KB Output is correct
37 Correct 472 ms 57032 KB Output is correct
38 Correct 645 ms 125056 KB Output is correct
39 Correct 1047 ms 142244 KB Output is correct
40 Correct 1361 ms 159288 KB Output is correct
41 Correct 1692 ms 177416 KB Output is correct
42 Correct 2100 ms 194968 KB Output is correct
43 Correct 42 ms 78544 KB Output is correct
44 Correct 46 ms 78540 KB Output is correct
45 Correct 42 ms 78524 KB Output is correct
46 Correct 18 ms 28492 KB Output is correct
47 Correct 18 ms 28476 KB Output is correct
48 Correct 43 ms 78532 KB Output is correct
49 Correct 46 ms 78612 KB Output is correct
50 Correct 45 ms 78516 KB Output is correct
51 Correct 45 ms 78516 KB Output is correct
52 Correct 19 ms 28492 KB Output is correct
53 Correct 43 ms 78564 KB Output is correct
54 Correct 21 ms 28980 KB Output is correct
55 Correct 23 ms 29316 KB Output is correct
56 Correct 638 ms 138360 KB Output is correct
57 Correct 1004 ms 165556 KB Output is correct
58 Correct 1083 ms 165624 KB Output is correct
59 Correct 18 ms 28396 KB Output is correct
60 Correct 44 ms 78556 KB Output is correct
61 Correct 18 ms 28492 KB Output is correct
62 Correct 1375 ms 213272 KB Output is correct
63 Correct 1305 ms 213280 KB Output is correct
64 Correct 1398 ms 212792 KB Output is correct
65 Correct 28 ms 29644 KB Output is correct
66 Correct 34 ms 30724 KB Output is correct
67 Correct 650 ms 138032 KB Output is correct
68 Correct 1028 ms 168268 KB Output is correct
69 Correct 1400 ms 197740 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28492 KB Output is correct
2 Correct 46 ms 78532 KB Output is correct
3 Correct 17 ms 28484 KB Output is correct
4 Correct 45 ms 78512 KB Output is correct
5 Correct 45 ms 78548 KB Output is correct
6 Correct 17 ms 28460 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 19 ms 28492 KB Output is correct
9 Correct 554 ms 145976 KB Output is correct
10 Correct 73 ms 85508 KB Output is correct
11 Correct 262 ms 115192 KB Output is correct
12 Correct 93 ms 89028 KB Output is correct
13 Correct 90 ms 41132 KB Output is correct
14 Correct 20 ms 28716 KB Output is correct
15 Correct 26 ms 28996 KB Output is correct
16 Correct 533 ms 145848 KB Output is correct
17 Correct 1378 ms 213424 KB Output is correct
18 Correct 1359 ms 213380 KB Output is correct
19 Correct 1454 ms 190392 KB Output is correct
20 Correct 1476 ms 197112 KB Output is correct
21 Correct 1302 ms 192884 KB Output is correct
22 Correct 44 ms 78532 KB Output is correct
23 Correct 206 ms 97840 KB Output is correct
24 Correct 69 ms 34244 KB Output is correct
25 Correct 276 ms 48792 KB Output is correct
26 Correct 530 ms 63172 KB Output is correct
27 Correct 746 ms 138500 KB Output is correct
28 Correct 1020 ms 153388 KB Output is correct
29 Correct 1306 ms 168236 KB Output is correct
30 Correct 1524 ms 183236 KB Output is correct
31 Correct 1857 ms 198096 KB Output is correct
32 Correct 1367 ms 199484 KB Output is correct
33 Correct 1287 ms 213224 KB Output is correct
34 Correct 29 ms 29900 KB Output is correct
35 Correct 37 ms 30960 KB Output is correct
36 Correct 612 ms 138268 KB Output is correct
37 Correct 986 ms 168304 KB Output is correct
38 Correct 1391 ms 197976 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28492 KB Output is correct
2 Correct 46 ms 78532 KB Output is correct
3 Correct 17 ms 28484 KB Output is correct
4 Correct 45 ms 78512 KB Output is correct
5 Correct 45 ms 78548 KB Output is correct
6 Correct 17 ms 28460 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 19 ms 28492 KB Output is correct
9 Correct 554 ms 145976 KB Output is correct
10 Correct 73 ms 85508 KB Output is correct
11 Correct 262 ms 115192 KB Output is correct
12 Correct 93 ms 89028 KB Output is correct
13 Correct 90 ms 41132 KB Output is correct
14 Correct 20 ms 28716 KB Output is correct
15 Correct 26 ms 28996 KB Output is correct
16 Correct 533 ms 145848 KB Output is correct
17 Correct 43 ms 78508 KB Output is correct
18 Correct 43 ms 78552 KB Output is correct
19 Correct 44 ms 78532 KB Output is correct
20 Correct 44 ms 78564 KB Output is correct
21 Correct 17 ms 28424 KB Output is correct
22 Correct 44 ms 78584 KB Output is correct
23 Correct 1304 ms 190556 KB Output is correct
24 Correct 47 ms 78532 KB Output is correct
25 Correct 45 ms 79268 KB Output is correct
26 Correct 24 ms 29324 KB Output is correct
27 Correct 27 ms 29620 KB Output is correct
28 Correct 414 ms 123492 KB Output is correct
29 Correct 653 ms 145808 KB Output is correct
30 Correct 946 ms 168408 KB Output is correct
31 Correct 1293 ms 190668 KB Output is correct
32 Correct 47 ms 78532 KB Output is correct
33 Correct 45 ms 78668 KB Output is correct
34 Correct 44 ms 78608 KB Output is correct
35 Correct 18 ms 28420 KB Output is correct
36 Correct 18 ms 28384 KB Output is correct
37 Correct 43 ms 78540 KB Output is correct
38 Correct 42 ms 78544 KB Output is correct
39 Correct 41 ms 78584 KB Output is correct
40 Correct 52 ms 78528 KB Output is correct
41 Correct 18 ms 28492 KB Output is correct
42 Correct 45 ms 78592 KB Output is correct
43 Correct 21 ms 29004 KB Output is correct
44 Correct 22 ms 29268 KB Output is correct
45 Correct 570 ms 138312 KB Output is correct
46 Correct 872 ms 165552 KB Output is correct
47 Correct 864 ms 165688 KB Output is correct
48 Correct 44 ms 78600 KB Output is correct
49 Correct 45 ms 78612 KB Output is correct
50 Correct 45 ms 78600 KB Output is correct
51 Correct 46 ms 78532 KB Output is correct
52 Correct 44 ms 78536 KB Output is correct
53 Correct 46 ms 78532 KB Output is correct
54 Correct 45 ms 78572 KB Output is correct
55 Correct 1297 ms 191240 KB Output is correct
56 Correct 44 ms 78588 KB Output is correct
57 Correct 50 ms 79688 KB Output is correct
58 Correct 64 ms 82112 KB Output is correct
59 Correct 43 ms 31452 KB Output is correct
60 Correct 560 ms 137688 KB Output is correct
61 Correct 775 ms 155108 KB Output is correct
62 Correct 969 ms 171576 KB Output is correct
63 Correct 1363 ms 191192 KB Output is correct
64 Correct 19 ms 28492 KB Output is correct
65 Correct 45 ms 78568 KB Output is correct
66 Correct 19 ms 28404 KB Output is correct
67 Correct 1296 ms 213276 KB Output is correct
68 Correct 1195 ms 213368 KB Output is correct
69 Correct 1221 ms 212628 KB Output is correct
70 Correct 25 ms 29516 KB Output is correct
71 Correct 34 ms 30744 KB Output is correct
72 Correct 558 ms 138196 KB Output is correct
73 Correct 919 ms 168276 KB Output is correct
74 Correct 1225 ms 197860 KB Output is correct
75 Correct 1344 ms 199356 KB Output is correct
76 Correct 1298 ms 213424 KB Output is correct
77 Correct 28 ms 29832 KB Output is correct
78 Correct 41 ms 31064 KB Output is correct
79 Correct 584 ms 138204 KB Output is correct
80 Correct 913 ms 168308 KB Output is correct
81 Correct 1310 ms 197932 KB Output is correct
82 Correct 44 ms 78544 KB Output is correct
83 Correct 43 ms 78568 KB Output is correct
84 Correct 18 ms 28500 KB Output is correct
85 Correct 1264 ms 190152 KB Output is correct
86 Correct 1236 ms 190264 KB Output is correct
87 Correct 1340 ms 190192 KB Output is correct
88 Correct 1113 ms 193160 KB Output is correct
89 Correct 643 ms 62132 KB Output is correct
90 Correct 1205 ms 85708 KB Output is correct
91 Correct 1197 ms 85684 KB Output is correct
92 Correct 1576 ms 213180 KB Output is correct
93 Correct 1515 ms 213168 KB Output is correct
94 Correct 1640 ms 213172 KB Output is correct
95 Correct 1575 ms 213092 KB Output is correct
96 Correct 52 ms 78532 KB Output is correct
97 Correct 114 ms 87168 KB Output is correct
98 Correct 235 ms 45348 KB Output is correct
99 Correct 1443 ms 190344 KB Output is correct
100 Correct 53 ms 31240 KB Output is correct
101 Correct 172 ms 42852 KB Output is correct
102 Correct 472 ms 57032 KB Output is correct
103 Correct 645 ms 125056 KB Output is correct
104 Correct 1047 ms 142244 KB Output is correct
105 Correct 1361 ms 159288 KB Output is correct
106 Correct 1692 ms 177416 KB Output is correct
107 Correct 2100 ms 194968 KB Output is correct
108 Correct 42 ms 78544 KB Output is correct
109 Correct 46 ms 78540 KB Output is correct
110 Correct 42 ms 78524 KB Output is correct
111 Correct 18 ms 28492 KB Output is correct
112 Correct 18 ms 28476 KB Output is correct
113 Correct 43 ms 78532 KB Output is correct
114 Correct 46 ms 78612 KB Output is correct
115 Correct 45 ms 78516 KB Output is correct
116 Correct 45 ms 78516 KB Output is correct
117 Correct 19 ms 28492 KB Output is correct
118 Correct 43 ms 78564 KB Output is correct
119 Correct 21 ms 28980 KB Output is correct
120 Correct 23 ms 29316 KB Output is correct
121 Correct 638 ms 138360 KB Output is correct
122 Correct 1004 ms 165556 KB Output is correct
123 Correct 1083 ms 165624 KB Output is correct
124 Correct 18 ms 28396 KB Output is correct
125 Correct 44 ms 78556 KB Output is correct
126 Correct 18 ms 28492 KB Output is correct
127 Correct 1375 ms 213272 KB Output is correct
128 Correct 1305 ms 213280 KB Output is correct
129 Correct 1398 ms 212792 KB Output is correct
130 Correct 28 ms 29644 KB Output is correct
131 Correct 34 ms 30724 KB Output is correct
132 Correct 650 ms 138032 KB Output is correct
133 Correct 1028 ms 168268 KB Output is correct
134 Correct 1400 ms 197740 KB Output is correct
135 Correct 1378 ms 213424 KB Output is correct
136 Correct 1359 ms 213380 KB Output is correct
137 Correct 1454 ms 190392 KB Output is correct
138 Correct 1476 ms 197112 KB Output is correct
139 Correct 1302 ms 192884 KB Output is correct
140 Correct 44 ms 78532 KB Output is correct
141 Correct 206 ms 97840 KB Output is correct
142 Correct 69 ms 34244 KB Output is correct
143 Correct 276 ms 48792 KB Output is correct
144 Correct 530 ms 63172 KB Output is correct
145 Correct 746 ms 138500 KB Output is correct
146 Correct 1020 ms 153388 KB Output is correct
147 Correct 1306 ms 168236 KB Output is correct
148 Correct 1524 ms 183236 KB Output is correct
149 Correct 1857 ms 198096 KB Output is correct
150 Correct 1367 ms 199484 KB Output is correct
151 Correct 1287 ms 213224 KB Output is correct
152 Correct 29 ms 29900 KB Output is correct
153 Correct 37 ms 30960 KB Output is correct
154 Correct 612 ms 138268 KB Output is correct
155 Correct 986 ms 168304 KB Output is correct
156 Correct 1391 ms 197976 KB Output is correct
157 Correct 50 ms 78576 KB Output is correct
158 Correct 19 ms 28436 KB Output is correct
159 Correct 51 ms 78532 KB Output is correct
160 Correct 49 ms 78516 KB Output is correct
161 Correct 1518 ms 192328 KB Output is correct
162 Correct 1436 ms 190300 KB Output is correct
163 Correct 1391 ms 191396 KB Output is correct
164 Correct 1372 ms 191164 KB Output is correct
165 Correct 1443 ms 191664 KB Output is correct
166 Correct 1503 ms 192148 KB Output is correct
167 Execution timed out 3618 ms 627116 KB Time limit exceeded
168 Halted 0 ms 0 KB -