oj.uz

Submission #1061712

# Submission time Handle Problem Language Result Execution time Memory
1061712 2024-08-16T12:06:25 Z mc061 Fountain Parks (IOI21_parks) C++17
15 / 100
 756 ms 66064 KB 
#include <bits/stdc++.h>
using namespace std;

map<pair<int, int>, int> vid;
int di[2] = {2, 0};
int dj[2] = {0, 2};

struct edge {
    int i1, j1, i2, j2;
};

vector<edge> edges;
const int N = 2e5+6;
struct DSU {
    int p[N]={};
    int sz[N];
    DSU() {
        iota(p, p+N, 0);
        fill(sz, sz+N, 1);
    }
    int get(int a) {
        return p[a] = (a == p[a] ? a : get(p[a]));
    }
    void merge(int a, int b) {
        int x = get(a), y = get(b);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
};

vector<edge> horizontal, vertical;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
bool try_build() {
    //0 - up(hor)   (from road: -1;+1)
    //1 - down(hor) (from road: +1;+1)
    //2 - left(ver) (from road: +1;-1)
    //3 - right(ver)(from road: +1;+1)

    vector<int> tlx = {-1, 1, 1, 1};
    vector<int> tly = {1, 1, -1, 1};

    vector<int> dx = {0, 0, 2, 2};
    vector<int> dy = {2, 2, 0, 0};

    map<pair<int, int>, int> bench_dir;
    for (const auto& e : horizontal) {
        bench_dir[{e.i1-1, e.j1+1}] = 0;
    }
    
    auto sieve_down = [&] (int bi, int bj) -> void {
        bench_dir.erase({bi, bj});
        bi += 2;
        while (bench_dir.count({bi, bj})) {
            bench_dir[{bi, bj}] = 1;
            bi += 2;
        }
        bench_dir[{bi, bj}] = 1;
    };

    for (const auto& e : vertical) {
        int wi_left = e.i1+1;
        int wj_left = e.j1-1;

        int wi_right = e.i1+1;
        int wj_right = e.j1+1;

        if (bench_dir.count({wi_left, wj_left})) {
            if (!bench_dir.count({wi_right, wj_right})) {
                bench_dir[{wi_right, wj_right}] = 3;
                continue;
            }
            int prev_dir = bench_dir[{wi_left, wj_left}];
            
            if (prev_dir == 0) {
                sieve_down(wi_left, wj_left);
                bench_dir[{wi_left, wj_left}] = 2;
                continue;
            }
            if (prev_dir == 1) {
                int prev_dir2 = bench_dir[{wi_right, wj_right}];
                if (prev_dir2 == 1) {
                    return false;
                }
            }
            sieve_down(wi_right, wj_right);
            bench_dir[{wi_right, wj_right}] = 3;
        }
        else {
            bench_dir[{wi_left, wj_left}] = 2;
        }
    }
    map<array<int, 4>, pair<int, int>> road_to_bench;
    for (const auto& [x, y] : bench_dir) {         
        int tx = x.first-tlx[y];
        int ty = x.second-tly[y];
        int bx = tx+dx[y];
        int by = ty+dy[y];
        road_to_bench[{tx, ty, bx, by}] = {x.first, x.second};
    }

    vector<int> u, v, a, b;

    for (const auto& e : horizontal) {
        u.push_back(vid[{e.i1, e.j1}]);
        v.push_back(vid[{e.i2, e.j2}]);
        a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first);
        b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second);
    }
    for (const auto& e : vertical) {
        u.push_back(vid[{e.i1, e.j1}]);
        v.push_back(vid[{e.i2, e.j2}]);
        a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first);
        b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second);
    }
    build(u, v, a, b);
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    const int n = x.size();
    for (int i = 0; i < n; ++i) {
        vid[{x[i], y[i]}] = i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            int ni = x[i] + di[j];
            int nj = y[i] + dj[j];
            auto it = vid.find({ni, nj});
            if (it == vid.end()) continue;
            edges.push_back({x[i], y[i], ni, nj});
        }
    }

    DSU d;
    for (const edge& e : edges) {
        bool hor = e.i1 == e.i2;
        int id1 = vid[{e.i1, e.j1}];
        int id2 = vid[{e.i2, e.j2}];
        if (d.get(id1) == d.get(id2)) continue;
        d.merge(id1, id2);
        if (!hor) vertical.push_back(e);
        else horizontal.push_back(e);
    }

    if (d.sz[d.get(0)] != n) return 0;

    sort(vertical.begin(), vertical.end(), [&](const edge& a, const edge& b) {
        if (a.i1 != b.i1) return a.i1 < b.i1;
        return a.j1 < b.j1; 
    });
    for (int i = 0; i < 5; ++i) {
        int j = try_build();
        if (j == 1) return true;
    }
    return false;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 293 ms 31728 KB Output is correct
10 Correct 14 ms 4952 KB Output is correct
11 Correct 81 ms 17736 KB Output is correct
12 Correct 23 ms 6480 KB Output is correct
13 Correct 26 ms 7628 KB Output is correct
14 Correct 3 ms 1888 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 273 ms 31656 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 293 ms 31728 KB Output is correct
10 Correct 14 ms 4952 KB Output is correct
11 Correct 81 ms 17736 KB Output is correct
12 Correct 23 ms 6480 KB Output is correct
13 Correct 26 ms 7628 KB Output is correct
14 Correct 3 ms 1888 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 273 ms 31656 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1880 KB Output is correct
21 Correct 1 ms 1884 KB Output is correct
22 Correct 1 ms 1968 KB Output is correct
23 Correct 752 ms 65676 KB Output is correct
24 Correct 2 ms 1884 KB Output is correct
25 Correct 4 ms 2396 KB Output is correct
26 Correct 3 ms 2396 KB Output is correct
27 Correct 5 ms 2544 KB Output is correct
28 Correct 239 ms 27204 KB Output is correct
29 Correct 387 ms 40212 KB Output is correct
30 Correct 561 ms 53072 KB Output is correct
31 Correct 745 ms 66064 KB Output is correct
32 Correct 1 ms 1880 KB Output is correct
33 Correct 1 ms 1880 KB Output is correct
34 Correct 2 ms 1884 KB Output is correct
35 Correct 1 ms 1884 KB Output is correct
36 Correct 1 ms 1884 KB Output is correct
37 Correct 1 ms 1884 KB Output is correct
38 Correct 2 ms 1884 KB Output is correct
39 Correct 1 ms 1880 KB Output is correct
40 Correct 1 ms 1880 KB Output is correct
41 Correct 1 ms 1884 KB Output is correct
42 Correct 1 ms 1884 KB Output is correct
43 Correct 3 ms 2140 KB Output is correct
44 Correct 3 ms 2396 KB Output is correct
45 Correct 282 ms 32608 KB Output is correct
46 Correct 464 ms 49236 KB Output is correct
47 Correct 471 ms 47900 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 293 ms 31728 KB Output is correct
10 Correct 14 ms 4952 KB Output is correct
11 Correct 81 ms 17736 KB Output is correct
12 Correct 23 ms 6480 KB Output is correct
13 Correct 26 ms 7628 KB Output is correct
14 Correct 3 ms 1888 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 273 ms 31656 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1880 KB Output is correct
21 Correct 1 ms 1884 KB Output is correct
22 Correct 1 ms 1968 KB Output is correct
23 Correct 752 ms 65676 KB Output is correct
24 Correct 2 ms 1884 KB Output is correct
25 Correct 4 ms 2396 KB Output is correct
26 Correct 3 ms 2396 KB Output is correct
27 Correct 5 ms 2544 KB Output is correct
28 Correct 239 ms 27204 KB Output is correct
29 Correct 387 ms 40212 KB Output is correct
30 Correct 561 ms 53072 KB Output is correct
31 Correct 745 ms 66064 KB Output is correct
32 Correct 1 ms 1880 KB Output is correct
33 Correct 1 ms 1880 KB Output is correct
34 Correct 2 ms 1884 KB Output is correct
35 Correct 1 ms 1884 KB Output is correct
36 Correct 1 ms 1884 KB Output is correct
37 Correct 1 ms 1884 KB Output is correct
38 Correct 2 ms 1884 KB Output is correct
39 Correct 1 ms 1880 KB Output is correct
40 Correct 1 ms 1880 KB Output is correct
41 Correct 1 ms 1884 KB Output is correct
42 Correct 1 ms 1884 KB Output is correct
43 Correct 3 ms 2140 KB Output is correct
44 Correct 3 ms 2396 KB Output is correct
45 Correct 282 ms 32608 KB Output is correct
46 Correct 464 ms 49236 KB Output is correct
47 Correct 471 ms 47900 KB Output is correct
48 Correct 2 ms 1884 KB Output is correct
49 Correct 2 ms 2136 KB Output is correct
50 Correct 1 ms 1884 KB Output is correct
51 Correct 1 ms 1884 KB Output is correct
52 Correct 1 ms 1880 KB Output is correct
53 Correct 1 ms 1884 KB Output is correct
54 Correct 1 ms 1888 KB Output is correct
55 Incorrect 756 ms 38588 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 293 ms 31728 KB Output is correct
10 Correct 14 ms 4952 KB Output is correct
11 Correct 81 ms 17736 KB Output is correct
12 Correct 23 ms 6480 KB Output is correct
13 Correct 26 ms 7628 KB Output is correct
14 Correct 3 ms 1888 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 273 ms 31656 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 2 ms 1888 KB Output is correct
20 Correct 644 ms 62972 KB Output is correct
21 Correct 668 ms 62784 KB Output is correct
22 Correct 661 ms 63012 KB Output is correct
23 Correct 484 ms 54632 KB Output is correct
24 Correct 229 ms 17624 KB Output is correct
25 Correct 470 ms 27564 KB Output is correct
26 Correct 279 ms 26820 KB Output is correct
27 Correct 728 ms 61756 KB Output is correct
28 Correct 704 ms 62252 KB Output is correct
29 Correct 604 ms 61592 KB Output is correct
30 Correct 649 ms 61620 KB Output is correct
31 Correct 1 ms 1884 KB Output is correct
32 Correct 28 ms 6364 KB Output is correct
33 Correct 81 ms 9812 KB Output is correct
34 Correct 712 ms 62500 KB Output is correct
35 Correct 14 ms 3164 KB Output is correct
36 Correct 66 ms 7808 KB Output is correct
37 Correct 164 ms 14320 KB Output is correct
38 Incorrect 193 ms 13772 KB Solution announced impossible, but it is possible.
39 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 293 ms 31728 KB Output is correct
10 Correct 14 ms 4952 KB Output is correct
11 Correct 81 ms 17736 KB Output is correct
12 Correct 23 ms 6480 KB Output is correct
13 Correct 26 ms 7628 KB Output is correct
14 Correct 3 ms 1888 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 273 ms 31656 KB Output is correct
17 Correct 711 ms 62048 KB Output is correct
18 Correct 705 ms 62660 KB Output is correct
19 Correct 634 ms 62484 KB Output is correct
20 Correct 702 ms 61376 KB Output is correct
21 Correct 593 ms 55588 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Incorrect 82 ms 6952 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 293 ms 31728 KB Output is correct
10 Correct 14 ms 4952 KB Output is correct
11 Correct 81 ms 17736 KB Output is correct
12 Correct 23 ms 6480 KB Output is correct
13 Correct 26 ms 7628 KB Output is correct
14 Correct 3 ms 1888 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 273 ms 31656 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1880 KB Output is correct
21 Correct 1 ms 1884 KB Output is correct
22 Correct 1 ms 1968 KB Output is correct
23 Correct 752 ms 65676 KB Output is correct
24 Correct 2 ms 1884 KB Output is correct
25 Correct 4 ms 2396 KB Output is correct
26 Correct 3 ms 2396 KB Output is correct
27 Correct 5 ms 2544 KB Output is correct
28 Correct 239 ms 27204 KB Output is correct
29 Correct 387 ms 40212 KB Output is correct
30 Correct 561 ms 53072 KB Output is correct
31 Correct 745 ms 66064 KB Output is correct
32 Correct 1 ms 1880 KB Output is correct
33 Correct 1 ms 1880 KB Output is correct
34 Correct 2 ms 1884 KB Output is correct
35 Correct 1 ms 1884 KB Output is correct
36 Correct 1 ms 1884 KB Output is correct
37 Correct 1 ms 1884 KB Output is correct
38 Correct 2 ms 1884 KB Output is correct
39 Correct 1 ms 1880 KB Output is correct
40 Correct 1 ms 1880 KB Output is correct
41 Correct 1 ms 1884 KB Output is correct
42 Correct 1 ms 1884 KB Output is correct
43 Correct 3 ms 2140 KB Output is correct
44 Correct 3 ms 2396 KB Output is correct
45 Correct 282 ms 32608 KB Output is correct
46 Correct 464 ms 49236 KB Output is correct
47 Correct 471 ms 47900 KB Output is correct
48 Correct 2 ms 1884 KB Output is correct
49 Correct 2 ms 2136 KB Output is correct
50 Correct 1 ms 1884 KB Output is correct
51 Correct 1 ms 1884 KB Output is correct
52 Correct 1 ms 1880 KB Output is correct
53 Correct 1 ms 1884 KB Output is correct
54 Correct 1 ms 1888 KB Output is correct
55 Incorrect 756 ms 38588 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -