oj.uz

Submission #797785

# Submission time Handle Problem Language Result Execution time Memory
797785 2023-07-29T22:25:10 Z Liudas Fountain Parks (IOI21_parks) C++17
15 / 100
 3077 ms 116592 KB 
#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
void dfs(int head, vector<vector<int>>&tree, vector<int> &vis){
    vis[head] = true;
    for(int i : tree[head]){
        if(!vis[i]){
            dfs(i, tree, vis);
        }
    }
}
int count_benches(vector<int> c, map<pair<int,int>, int> &taken){
    int s = 2;
    if(c[0] != c[2]){
        s -= taken[{c[0] - (c[0]-c[2])/2, c[1] + 1}];
        s -= taken[{c[0] - (c[0]-c[2])/2, c[1] - 1}];
    }
    else{
        s -= taken[{c[0] + 1, c[1] - (c[1] - c[3]) / 2}];
        s -= taken[{c[0] - 1, c[1] - (c[1] - c[3]) / 2}];
    }
    return s;
}
int construct_roads(vector<int> x, vector<int> y){
    int N = x.size();
    vector<vector<int>> tree(N);
    map<pair<int,int>, int> arr, bench, taken;
    map<array<int, 4>, bool> road;
    for(int i = 0; i < N; i ++){
        arr[{x[i], y[i]}] = i;
    }
    vector<int> dx = {-2, 2, 0, 0}, dy = {0,0,2,-2};
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < 4; j ++){
            if(arr.find({x[i] + dx[j], y[i] + dy[j]}) != arr.end()){
                tree[i].push_back(arr[{x[i] + dx[j], y[i] + dy[j]}]);
                road[{x[i], y[i], x[i]+dx[j], y[i] + dy[j]}] = true;
                road[{x[i]+dx[j], y[i] + dy[j], x[i], y[i]}] = true;
                if(dx[j]){
                    bench[{x[i] + dx[j]/2, y[i] + 1}] ++;
                    bench[{x[i] + dx[j]/2, y[i] - 1}] ++;
                }
                if(dy[j]){
                    bench[{x[i] + 1, y[i] + dy[j] / 2}] ++;
                    bench[{x[i] - 1, y[i] + dy[j] / 2}] ++;
                }
            }
        }
    }
    vector<pair<int, int>> pairs;
    for(auto [l, r] : bench){
        pairs.push_back(l);
    }
    sort(pairs.begin(), pairs.end(), [&](pair<int, int> a, pair<int, int> b){return bench[a] < bench[b];});
    vector<int> vis(N, 0);
    dfs(0, tree, vis);
    for(int i : vis){
        if(!i){
            return 0;
        }
    }
    vector<int> ansu, ansv, ansa, ansb;
    for(auto[l ,r] : pairs){
        vector<int> dix = {1, -1, 1, -1}, diy = {-1, 1, 1, -1};
        int bi = -1, bj = -1, s = 1e9;
        for(int i = 0; i < 4; i ++){
            for(int j = 0; j < 4; j ++){
                int ss = 1e9;
                if(road.find({l + dix[i], r + diy[i], l + dix[j], r + diy[j]}) != road.end()){
                    ss = count_benches({l + dix[i], r + diy[i], l + dix[j], r + diy[j]}, taken);
                }
                if(s > ss){
                    s = ss;
                    bi = i;
                    bj = j;
                }
            }
        }
        if(bi + 1){
            road.erase({l + dix[bi], r + diy[bi], l + dix[bj], r + diy[bj]});
            road.erase({l + dix[bj], r + diy[bj], l + dix[bi], r + diy[bi]});
            ansu.push_back(arr[{l + dix[bi], r + diy[bi]}]);
            ansv.push_back(arr[{l + dix[bj], r + diy[bj]}]);
            ansa.push_back(l);
            ansb.push_back(r);
            taken[{l, r}] = true;
        }
    }
    build(ansv, ansu, ansa, ansb);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 982 ms 50792 KB Output is correct
10 Correct 60 ms 5376 KB Output is correct
11 Correct 458 ms 27604 KB Output is correct
12 Correct 105 ms 7764 KB Output is correct
13 Correct 258 ms 19840 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 7 ms 1144 KB Output is correct
16 Correct 994 ms 48932 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 982 ms 50792 KB Output is correct
10 Correct 60 ms 5376 KB Output is correct
11 Correct 458 ms 27604 KB Output is correct
12 Correct 105 ms 7764 KB Output is correct
13 Correct 258 ms 19840 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 7 ms 1144 KB Output is correct
16 Correct 994 ms 48932 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2980 ms 116592 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 8 ms 988 KB Output is correct
26 Correct 12 ms 1620 KB Output is correct
27 Correct 17 ms 2100 KB Output is correct
28 Correct 1022 ms 44684 KB Output is correct
29 Correct 1560 ms 67440 KB Output is correct
30 Correct 2373 ms 90864 KB Output is correct
31 Correct 3024 ms 115760 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 6 ms 980 KB Output is correct
44 Correct 10 ms 1468 KB Output is correct
45 Correct 1010 ms 44988 KB Output is correct
46 Correct 1633 ms 65724 KB Output is correct
47 Correct 1691 ms 65420 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 982 ms 50792 KB Output is correct
10 Correct 60 ms 5376 KB Output is correct
11 Correct 458 ms 27604 KB Output is correct
12 Correct 105 ms 7764 KB Output is correct
13 Correct 258 ms 19840 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 7 ms 1144 KB Output is correct
16 Correct 994 ms 48932 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2980 ms 116592 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 8 ms 988 KB Output is correct
26 Correct 12 ms 1620 KB Output is correct
27 Correct 17 ms 2100 KB Output is correct
28 Correct 1022 ms 44684 KB Output is correct
29 Correct 1560 ms 67440 KB Output is correct
30 Correct 2373 ms 90864 KB Output is correct
31 Correct 3024 ms 115760 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 6 ms 980 KB Output is correct
44 Correct 10 ms 1468 KB Output is correct
45 Correct 1010 ms 44988 KB Output is correct
46 Correct 1633 ms 65724 KB Output is correct
47 Correct 1691 ms 65420 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 0 ms 296 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 296 KB Output is correct
55 Correct 3077 ms 113136 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Correct 12 ms 1304 KB Output is correct
58 Correct 45 ms 3612 KB Output is correct
59 Correct 47 ms 4888 KB Output is correct
60 Incorrect 1297 ms 56224 KB Given structure is not connected: There is no path between vertices 0 and 35744
61 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 982 ms 50792 KB Output is correct
10 Correct 60 ms 5376 KB Output is correct
11 Correct 458 ms 27604 KB Output is correct
12 Correct 105 ms 7764 KB Output is correct
13 Correct 258 ms 19840 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 7 ms 1144 KB Output is correct
16 Correct 994 ms 48932 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1891 ms 88800 KB Output is correct
21 Correct 1937 ms 86236 KB Output is correct
22 Correct 1905 ms 85540 KB Output is correct
23 Correct 2023 ms 84840 KB Output is correct
24 Correct 277 ms 23232 KB Output is correct
25 Correct 2122 ms 82664 KB Output is correct
26 Correct 1823 ms 82748 KB Output is correct
27 Correct 2462 ms 92660 KB Output is correct
28 Correct 2425 ms 92712 KB Output is correct
29 Correct 2794 ms 92688 KB Output is correct
30 Correct 2796 ms 92632 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Incorrect 100 ms 6412 KB Given structure is not connected: There is no path between vertices 0 and 1
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 982 ms 50792 KB Output is correct
10 Correct 60 ms 5376 KB Output is correct
11 Correct 458 ms 27604 KB Output is correct
12 Correct 105 ms 7764 KB Output is correct
13 Correct 258 ms 19840 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 7 ms 1144 KB Output is correct
16 Correct 994 ms 48932 KB Output is correct
17 Correct 2340 ms 102400 KB Output is correct
18 Correct 2316 ms 101652 KB Output is correct
19 Incorrect 1969 ms 88076 KB Given structure is not connected: There is no path between vertices 0 and 103320
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 982 ms 50792 KB Output is correct
10 Correct 60 ms 5376 KB Output is correct
11 Correct 458 ms 27604 KB Output is correct
12 Correct 105 ms 7764 KB Output is correct
13 Correct 258 ms 19840 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 7 ms 1144 KB Output is correct
16 Correct 994 ms 48932 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2980 ms 116592 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 8 ms 988 KB Output is correct
26 Correct 12 ms 1620 KB Output is correct
27 Correct 17 ms 2100 KB Output is correct
28 Correct 1022 ms 44684 KB Output is correct
29 Correct 1560 ms 67440 KB Output is correct
30 Correct 2373 ms 90864 KB Output is correct
31 Correct 3024 ms 115760 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 6 ms 980 KB Output is correct
44 Correct 10 ms 1468 KB Output is correct
45 Correct 1010 ms 44988 KB Output is correct
46 Correct 1633 ms 65724 KB Output is correct
47 Correct 1691 ms 65420 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 0 ms 296 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 296 KB Output is correct
55 Correct 3077 ms 113136 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Correct 12 ms 1304 KB Output is correct
58 Correct 45 ms 3612 KB Output is correct
59 Correct 47 ms 4888 KB Output is correct
60 Incorrect 1297 ms 56224 KB Given structure is not connected: There is no path between vertices 0 and 35744
61 Halted 0 ms 0 KB -