답안 #439965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439965	2021-07-01T10:10:32 Z	cheeheng	분수 공원 (IOI21_parks)	C++17	70 / 100	1201 ms	230660 KB

parks

#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> indxEdge;
map<ii, int> indxBench;

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

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

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

    int m = 0;
    for(int i = 0; i < n; i ++){
        int i2 = p[i];
        for(int k = 0; k < 4; k ++){
            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();
    uf->init(n);

    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].insert(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);
    assert(res == n-1);

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

    assert(cnt2 == n-1);

    build(U, V, A, B);
    return 1;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	33100 KB	Output is correct
2	Correct	46 ms	83204 KB	Output is correct
3	Correct	22 ms	33100 KB	Output is correct
4	Correct	45 ms	83232 KB	Output is correct
5	Correct	46 ms	83296 KB	Output is correct
6	Correct	22 ms	33316 KB	Output is correct
7	Correct	22 ms	33092 KB	Output is correct
8	Correct	21 ms	33184 KB	Output is correct
9	Correct	494 ms	156924 KB	Output is correct
10	Correct	74 ms	90820 KB	Output is correct
11	Correct	242 ms	123192 KB	Output is correct
12	Correct	90 ms	94668 KB	Output is correct
13	Correct	83 ms	42948 KB	Output is correct
14	Correct	22 ms	33356 KB	Output is correct
15	Correct	24 ms	33548 KB	Output is correct
16	Correct	512 ms	156832 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	33100 KB	Output is correct
2	Correct	46 ms	83204 KB	Output is correct
3	Correct	22 ms	33100 KB	Output is correct
4	Correct	45 ms	83232 KB	Output is correct
5	Correct	46 ms	83296 KB	Output is correct
6	Correct	22 ms	33316 KB	Output is correct
7	Correct	22 ms	33092 KB	Output is correct
8	Correct	21 ms	33184 KB	Output is correct
9	Correct	494 ms	156924 KB	Output is correct
10	Correct	74 ms	90820 KB	Output is correct
11	Correct	242 ms	123192 KB	Output is correct
12	Correct	90 ms	94668 KB	Output is correct
13	Correct	83 ms	42948 KB	Output is correct
14	Correct	22 ms	33356 KB	Output is correct
15	Correct	24 ms	33548 KB	Output is correct
16	Correct	512 ms	156832 KB	Output is correct
17	Correct	43 ms	83328 KB	Output is correct
18	Correct	48 ms	83220 KB	Output is correct
19	Correct	46 ms	83276 KB	Output is correct
20	Correct	44 ms	83360 KB	Output is correct
21	Correct	20 ms	33100 KB	Output is correct
22	Correct	44 ms	83220 KB	Output is correct
23	Correct	1051 ms	201612 KB	Output is correct
24	Correct	43 ms	83276 KB	Output is correct
25	Correct	47 ms	83952 KB	Output is correct
26	Correct	25 ms	33868 KB	Output is correct
27	Correct	29 ms	34048 KB	Output is correct
28	Correct	357 ms	130548 KB	Output is correct
29	Correct	585 ms	154300 KB	Output is correct
30	Correct	886 ms	177848 KB	Output is correct
31	Correct	1027 ms	201576 KB	Output is correct
32	Correct	46 ms	83248 KB	Output is correct
33	Correct	42 ms	83256 KB	Output is correct
34	Correct	46 ms	83200 KB	Output is correct
35	Correct	22 ms	33128 KB	Output is correct
36	Correct	20 ms	33092 KB	Output is correct
37	Correct	45 ms	83228 KB	Output is correct
38	Correct	47 ms	83276 KB	Output is correct
39	Correct	46 ms	83288 KB	Output is correct
40	Correct	44 ms	83248 KB	Output is correct
41	Correct	20 ms	33056 KB	Output is correct
42	Correct	45 ms	83324 KB	Output is correct
43	Correct	23 ms	33640 KB	Output is correct
44	Correct	25 ms	33832 KB	Output is correct
45	Correct	529 ms	147440 KB	Output is correct
46	Correct	809 ms	176552 KB	Output is correct
47	Correct	760 ms	176568 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	33100 KB	Output is correct
2	Correct	46 ms	83204 KB	Output is correct
3	Correct	22 ms	33100 KB	Output is correct
4	Correct	45 ms	83232 KB	Output is correct
5	Correct	46 ms	83296 KB	Output is correct
6	Correct	22 ms	33316 KB	Output is correct
7	Correct	22 ms	33092 KB	Output is correct
8	Correct	21 ms	33184 KB	Output is correct
9	Correct	494 ms	156924 KB	Output is correct
10	Correct	74 ms	90820 KB	Output is correct
11	Correct	242 ms	123192 KB	Output is correct
12	Correct	90 ms	94668 KB	Output is correct
13	Correct	83 ms	42948 KB	Output is correct
14	Correct	22 ms	33356 KB	Output is correct
15	Correct	24 ms	33548 KB	Output is correct
16	Correct	512 ms	156832 KB	Output is correct
17	Correct	43 ms	83328 KB	Output is correct
18	Correct	48 ms	83220 KB	Output is correct
19	Correct	46 ms	83276 KB	Output is correct
20	Correct	44 ms	83360 KB	Output is correct
21	Correct	20 ms	33100 KB	Output is correct
22	Correct	44 ms	83220 KB	Output is correct
23	Correct	1051 ms	201612 KB	Output is correct
24	Correct	43 ms	83276 KB	Output is correct
25	Correct	47 ms	83952 KB	Output is correct
26	Correct	25 ms	33868 KB	Output is correct
27	Correct	29 ms	34048 KB	Output is correct
28	Correct	357 ms	130548 KB	Output is correct
29	Correct	585 ms	154300 KB	Output is correct
30	Correct	886 ms	177848 KB	Output is correct
31	Correct	1027 ms	201576 KB	Output is correct
32	Correct	46 ms	83248 KB	Output is correct
33	Correct	42 ms	83256 KB	Output is correct
34	Correct	46 ms	83200 KB	Output is correct
35	Correct	22 ms	33128 KB	Output is correct
36	Correct	20 ms	33092 KB	Output is correct
37	Correct	45 ms	83228 KB	Output is correct
38	Correct	47 ms	83276 KB	Output is correct
39	Correct	46 ms	83288 KB	Output is correct
40	Correct	44 ms	83248 KB	Output is correct
41	Correct	20 ms	33056 KB	Output is correct
42	Correct	45 ms	83324 KB	Output is correct
43	Correct	23 ms	33640 KB	Output is correct
44	Correct	25 ms	33832 KB	Output is correct
45	Correct	529 ms	147440 KB	Output is correct
46	Correct	809 ms	176552 KB	Output is correct
47	Correct	760 ms	176568 KB	Output is correct
48	Correct	44 ms	83276 KB	Output is correct
49	Correct	44 ms	83204 KB	Output is correct
50	Correct	46 ms	83220 KB	Output is correct
51	Correct	45 ms	83276 KB	Output is correct
52	Correct	41 ms	83268 KB	Output is correct
53	Correct	45 ms	83316 KB	Output is correct
54	Correct	47 ms	83296 KB	Output is correct
55	Correct	1122 ms	202164 KB	Output is correct
56	Correct	44 ms	83312 KB	Output is correct
57	Correct	51 ms	84416 KB	Output is correct
58	Correct	64 ms	86976 KB	Output is correct
59	Correct	39 ms	35496 KB	Output is correct
60	Correct	484 ms	145560 KB	Output is correct
61	Correct	656 ms	163972 KB	Output is correct
62	Correct	876 ms	181492 KB	Output is correct
63	Correct	1102 ms	202020 KB	Output is correct
64	Correct	20 ms	33100 KB	Output is correct
65	Correct	43 ms	83268 KB	Output is correct
66	Correct	22 ms	33080 KB	Output is correct
67	Correct	1138 ms	230584 KB	Output is correct
68	Correct	1108 ms	230640 KB	Output is correct
69	Correct	1125 ms	229808 KB	Output is correct
70	Correct	28 ms	33996 KB	Output is correct
71	Correct	33 ms	34924 KB	Output is correct
72	Correct	477 ms	146672 KB	Output is correct
73	Correct	800 ms	178568 KB	Output is correct
74	Correct	1122 ms	210064 KB	Output is correct
75	Correct	1091 ms	213024 KB	Output is correct
76	Correct	1101 ms	230480 KB	Output is correct
77	Correct	29 ms	34216 KB	Output is correct
78	Correct	33 ms	35148 KB	Output is correct
79	Correct	476 ms	146720 KB	Output is correct
80	Correct	792 ms	178704 KB	Output is correct
81	Correct	1088 ms	210356 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	33100 KB	Output is correct
2	Correct	46 ms	83204 KB	Output is correct
3	Correct	22 ms	33100 KB	Output is correct
4	Correct	45 ms	83232 KB	Output is correct
5	Correct	46 ms	83296 KB	Output is correct
6	Correct	22 ms	33316 KB	Output is correct
7	Correct	22 ms	33092 KB	Output is correct
8	Correct	21 ms	33184 KB	Output is correct
9	Correct	494 ms	156924 KB	Output is correct
10	Correct	74 ms	90820 KB	Output is correct
11	Correct	242 ms	123192 KB	Output is correct
12	Correct	90 ms	94668 KB	Output is correct
13	Correct	83 ms	42948 KB	Output is correct
14	Correct	22 ms	33356 KB	Output is correct
15	Correct	24 ms	33548 KB	Output is correct
16	Correct	512 ms	156832 KB	Output is correct
17	Correct	42 ms	83336 KB	Output is correct
18	Correct	45 ms	83288 KB	Output is correct
19	Correct	21 ms	33120 KB	Output is correct
20	Correct	954 ms	200072 KB	Output is correct
21	Correct	957 ms	200056 KB	Output is correct
22	Correct	1036 ms	200284 KB	Output is correct
23	Correct	855 ms	208488 KB	Output is correct
24	Correct	274 ms	54288 KB	Output is correct
25	Correct	598 ms	77780 KB	Output is correct
26	Correct	601 ms	77888 KB	Output is correct
27	Correct	1105 ms	230456 KB	Output is correct
28	Correct	987 ms	230448 KB	Output is correct
29	Correct	1068 ms	230416 KB	Output is correct
30	Correct	1050 ms	230456 KB	Output is correct
31	Correct	46 ms	83236 KB	Output is correct
32	Correct	95 ms	92532 KB	Output is correct
33	Correct	130 ms	43744 KB	Output is correct
34	Correct	990 ms	200108 KB	Output is correct
35	Correct	38 ms	35404 KB	Output is correct
36	Correct	114 ms	44288 KB	Output is correct
37	Correct	251 ms	55480 KB	Output is correct
38	Correct	463 ms	132668 KB	Output is correct
39	Correct	651 ms	151100 KB	Output is correct
40	Correct	816 ms	169916 KB	Output is correct
41	Correct	1057 ms	187632 KB	Output is correct
42	Correct	1122 ms	206772 KB	Output is correct
43	Correct	42 ms	83292 KB	Output is correct
44	Correct	42 ms	83276 KB	Output is correct
45	Correct	47 ms	83312 KB	Output is correct
46	Correct	22 ms	33144 KB	Output is correct
47	Correct	20 ms	33188 KB	Output is correct
48	Correct	49 ms	83260 KB	Output is correct
49	Correct	44 ms	83272 KB	Output is correct
50	Correct	45 ms	83264 KB	Output is correct
51	Correct	43 ms	83404 KB	Output is correct
52	Correct	22 ms	33100 KB	Output is correct
53	Correct	47 ms	83216 KB	Output is correct
54	Correct	23 ms	33576 KB	Output is correct
55	Correct	25 ms	33812 KB	Output is correct
56	Correct	463 ms	147392 KB	Output is correct
57	Correct	694 ms	176572 KB	Output is correct
58	Correct	792 ms	176568 KB	Output is correct
59	Correct	22 ms	33100 KB	Output is correct
60	Correct	45 ms	83300 KB	Output is correct
61	Correct	23 ms	33100 KB	Output is correct
62	Correct	1117 ms	230600 KB	Output is correct
63	Correct	1124 ms	230588 KB	Output is correct
64	Correct	1145 ms	229956 KB	Output is correct
65	Correct	29 ms	33996 KB	Output is correct
66	Correct	36 ms	34976 KB	Output is correct
67	Correct	488 ms	146700 KB	Output is correct
68	Correct	802 ms	178616 KB	Output is correct
69	Correct	1127 ms	210084 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	33100 KB	Output is correct
2	Correct	46 ms	83204 KB	Output is correct
3	Correct	22 ms	33100 KB	Output is correct
4	Correct	45 ms	83232 KB	Output is correct
5	Correct	46 ms	83296 KB	Output is correct
6	Correct	22 ms	33316 KB	Output is correct
7	Correct	22 ms	33092 KB	Output is correct
8	Correct	21 ms	33184 KB	Output is correct
9	Correct	494 ms	156924 KB	Output is correct
10	Correct	74 ms	90820 KB	Output is correct
11	Correct	242 ms	123192 KB	Output is correct
12	Correct	90 ms	94668 KB	Output is correct
13	Correct	83 ms	42948 KB	Output is correct
14	Correct	22 ms	33356 KB	Output is correct
15	Correct	24 ms	33548 KB	Output is correct
16	Correct	512 ms	156832 KB	Output is correct
17	Correct	1116 ms	230488 KB	Output is correct
18	Correct	1099 ms	230660 KB	Output is correct
19	Correct	1032 ms	199988 KB	Output is correct
20	Correct	987 ms	209132 KB	Output is correct
21	Correct	989 ms	206748 KB	Output is correct
22	Correct	46 ms	83276 KB	Output is correct
23	Correct	170 ms	103744 KB	Output is correct
24	Correct	60 ms	37648 KB	Output is correct
25	Correct	195 ms	48980 KB	Output is correct
26	Correct	329 ms	60232 KB	Output is correct
27	Correct	545 ms	146488 KB	Output is correct
28	Correct	680 ms	162608 KB	Output is correct
29	Correct	861 ms	178144 KB	Output is correct
30	Correct	958 ms	194000 KB	Output is correct
31	Correct	1201 ms	209716 KB	Output is correct
32	Correct	1147 ms	212784 KB	Output is correct
33	Correct	1133 ms	230524 KB	Output is correct
34	Correct	29 ms	34252 KB	Output is correct
35	Correct	36 ms	35072 KB	Output is correct
36	Correct	519 ms	146608 KB	Output is correct
37	Correct	763 ms	178720 KB	Output is correct
38	Correct	1120 ms	210276 KB	Output is correct

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	33100 KB	Output is correct
2	Correct	46 ms	83204 KB	Output is correct
3	Correct	22 ms	33100 KB	Output is correct
4	Correct	45 ms	83232 KB	Output is correct
5	Correct	46 ms	83296 KB	Output is correct
6	Correct	22 ms	33316 KB	Output is correct
7	Correct	22 ms	33092 KB	Output is correct
8	Correct	21 ms	33184 KB	Output is correct
9	Correct	494 ms	156924 KB	Output is correct
10	Correct	74 ms	90820 KB	Output is correct
11	Correct	242 ms	123192 KB	Output is correct
12	Correct	90 ms	94668 KB	Output is correct
13	Correct	83 ms	42948 KB	Output is correct
14	Correct	22 ms	33356 KB	Output is correct
15	Correct	24 ms	33548 KB	Output is correct
16	Correct	512 ms	156832 KB	Output is correct
17	Correct	43 ms	83328 KB	Output is correct
18	Correct	48 ms	83220 KB	Output is correct
19	Correct	46 ms	83276 KB	Output is correct
20	Correct	44 ms	83360 KB	Output is correct
21	Correct	20 ms	33100 KB	Output is correct
22	Correct	44 ms	83220 KB	Output is correct
23	Correct	1051 ms	201612 KB	Output is correct
24	Correct	43 ms	83276 KB	Output is correct
25	Correct	47 ms	83952 KB	Output is correct
26	Correct	25 ms	33868 KB	Output is correct
27	Correct	29 ms	34048 KB	Output is correct
28	Correct	357 ms	130548 KB	Output is correct
29	Correct	585 ms	154300 KB	Output is correct
30	Correct	886 ms	177848 KB	Output is correct
31	Correct	1027 ms	201576 KB	Output is correct
32	Correct	46 ms	83248 KB	Output is correct
33	Correct	42 ms	83256 KB	Output is correct
34	Correct	46 ms	83200 KB	Output is correct
35	Correct	22 ms	33128 KB	Output is correct
36	Correct	20 ms	33092 KB	Output is correct
37	Correct	45 ms	83228 KB	Output is correct
38	Correct	47 ms	83276 KB	Output is correct
39	Correct	46 ms	83288 KB	Output is correct
40	Correct	44 ms	83248 KB	Output is correct
41	Correct	20 ms	33056 KB	Output is correct
42	Correct	45 ms	83324 KB	Output is correct
43	Correct	23 ms	33640 KB	Output is correct
44	Correct	25 ms	33832 KB	Output is correct
45	Correct	529 ms	147440 KB	Output is correct
46	Correct	809 ms	176552 KB	Output is correct
47	Correct	760 ms	176568 KB	Output is correct
48	Correct	44 ms	83276 KB	Output is correct
49	Correct	44 ms	83204 KB	Output is correct
50	Correct	46 ms	83220 KB	Output is correct
51	Correct	45 ms	83276 KB	Output is correct
52	Correct	41 ms	83268 KB	Output is correct
53	Correct	45 ms	83316 KB	Output is correct
54	Correct	47 ms	83296 KB	Output is correct
55	Correct	1122 ms	202164 KB	Output is correct
56	Correct	44 ms	83312 KB	Output is correct
57	Correct	51 ms	84416 KB	Output is correct
58	Correct	64 ms	86976 KB	Output is correct
59	Correct	39 ms	35496 KB	Output is correct
60	Correct	484 ms	145560 KB	Output is correct
61	Correct	656 ms	163972 KB	Output is correct
62	Correct	876 ms	181492 KB	Output is correct
63	Correct	1102 ms	202020 KB	Output is correct
64	Correct	20 ms	33100 KB	Output is correct
65	Correct	43 ms	83268 KB	Output is correct
66	Correct	22 ms	33080 KB	Output is correct
67	Correct	1138 ms	230584 KB	Output is correct
68	Correct	1108 ms	230640 KB	Output is correct
69	Correct	1125 ms	229808 KB	Output is correct
70	Correct	28 ms	33996 KB	Output is correct
71	Correct	33 ms	34924 KB	Output is correct
72	Correct	477 ms	146672 KB	Output is correct
73	Correct	800 ms	178568 KB	Output is correct
74	Correct	1122 ms	210064 KB	Output is correct
75	Correct	1091 ms	213024 KB	Output is correct
76	Correct	1101 ms	230480 KB	Output is correct
77	Correct	29 ms	34216 KB	Output is correct
78	Correct	33 ms	35148 KB	Output is correct
79	Correct	476 ms	146720 KB	Output is correct
80	Correct	792 ms	178704 KB	Output is correct
81	Correct	1088 ms	210356 KB	Output is correct
82	Correct	42 ms	83336 KB	Output is correct
83	Correct	45 ms	83288 KB	Output is correct
84	Correct	21 ms	33120 KB	Output is correct
85	Correct	954 ms	200072 KB	Output is correct
86	Correct	957 ms	200056 KB	Output is correct
87	Correct	1036 ms	200284 KB	Output is correct
88	Correct	855 ms	208488 KB	Output is correct
89	Correct	274 ms	54288 KB	Output is correct
90	Correct	598 ms	77780 KB	Output is correct
91	Correct	601 ms	77888 KB	Output is correct
92	Correct	1105 ms	230456 KB	Output is correct
93	Correct	987 ms	230448 KB	Output is correct
94	Correct	1068 ms	230416 KB	Output is correct
95	Correct	1050 ms	230456 KB	Output is correct
96	Correct	46 ms	83236 KB	Output is correct
97	Correct	95 ms	92532 KB	Output is correct
98	Correct	130 ms	43744 KB	Output is correct
99	Correct	990 ms	200108 KB	Output is correct
100	Correct	38 ms	35404 KB	Output is correct
101	Correct	114 ms	44288 KB	Output is correct
102	Correct	251 ms	55480 KB	Output is correct
103	Correct	463 ms	132668 KB	Output is correct
104	Correct	651 ms	151100 KB	Output is correct
105	Correct	816 ms	169916 KB	Output is correct
106	Correct	1057 ms	187632 KB	Output is correct
107	Correct	1122 ms	206772 KB	Output is correct
108	Correct	42 ms	83292 KB	Output is correct
109	Correct	42 ms	83276 KB	Output is correct
110	Correct	47 ms	83312 KB	Output is correct
111	Correct	22 ms	33144 KB	Output is correct
112	Correct	20 ms	33188 KB	Output is correct
113	Correct	49 ms	83260 KB	Output is correct
114	Correct	44 ms	83272 KB	Output is correct
115	Correct	45 ms	83264 KB	Output is correct
116	Correct	43 ms	83404 KB	Output is correct
117	Correct	22 ms	33100 KB	Output is correct
118	Correct	47 ms	83216 KB	Output is correct
119	Correct	23 ms	33576 KB	Output is correct
120	Correct	25 ms	33812 KB	Output is correct
121	Correct	463 ms	147392 KB	Output is correct
122	Correct	694 ms	176572 KB	Output is correct
123	Correct	792 ms	176568 KB	Output is correct
124	Correct	22 ms	33100 KB	Output is correct
125	Correct	45 ms	83300 KB	Output is correct
126	Correct	23 ms	33100 KB	Output is correct
127	Correct	1117 ms	230600 KB	Output is correct
128	Correct	1124 ms	230588 KB	Output is correct
129	Correct	1145 ms	229956 KB	Output is correct
130	Correct	29 ms	33996 KB	Output is correct
131	Correct	36 ms	34976 KB	Output is correct
132	Correct	488 ms	146700 KB	Output is correct
133	Correct	802 ms	178616 KB	Output is correct
134	Correct	1127 ms	210084 KB	Output is correct
135	Correct	1116 ms	230488 KB	Output is correct
136	Correct	1099 ms	230660 KB	Output is correct
137	Correct	1032 ms	199988 KB	Output is correct
138	Correct	987 ms	209132 KB	Output is correct
139	Correct	989 ms	206748 KB	Output is correct
140	Correct	46 ms	83276 KB	Output is correct
141	Correct	170 ms	103744 KB	Output is correct
142	Correct	60 ms	37648 KB	Output is correct
143	Correct	195 ms	48980 KB	Output is correct
144	Correct	329 ms	60232 KB	Output is correct
145	Correct	545 ms	146488 KB	Output is correct
146	Correct	680 ms	162608 KB	Output is correct
147	Correct	861 ms	178144 KB	Output is correct
148	Correct	958 ms	194000 KB	Output is correct
149	Correct	1201 ms	209716 KB	Output is correct
150	Correct	1147 ms	212784 KB	Output is correct
151	Correct	1133 ms	230524 KB	Output is correct
152	Correct	29 ms	34252 KB	Output is correct
153	Correct	36 ms	35072 KB	Output is correct
154	Correct	519 ms	146608 KB	Output is correct
155	Correct	763 ms	178720 KB	Output is correct
156	Correct	1120 ms	210276 KB	Output is correct
157	Correct	41 ms	83300 KB	Output is correct
158	Correct	21 ms	33100 KB	Output is correct
159	Correct	45 ms	83300 KB	Output is correct
160	Correct	47 ms	83252 KB	Output is correct
161	Correct	1078 ms	203248 KB	Output is correct
162	Correct	994 ms	199992 KB	Output is correct
163	Correct	1146 ms	201112 KB	Output is correct
164	Correct	1083 ms	201124 KB	Output is correct
165	Correct	1179 ms	203436 KB	Output is correct
166	Correct	1180 ms	203100 KB	Output is correct
167	Runtime error	677 ms	223148 KB	Execution killed with signal 6
168	Halted	0 ms	0 KB	-

답안 #439965

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 15.0 / 15.0

Subtask #4 20.0 / 20.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
15.0 / 15.0

Subtask #4
20.0 / 20.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 30.0