oj.uz

Submission #1061750

# Submission time Handle Problem Language Result Execution time Memory
1061750 2024-08-16T12:38:01 Z mc061 Fountain Parks (IOI21_parks) C++17
25 / 100
 2305 ms 66576 KB 
#pragma GCC optimize("Ofast")

#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() {
    // srand(69420);
    //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 if (prev_dir == 3) return false;
        }
        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;
    }
    vector<edge> all_vert;
    vector<edge> all_hor;
    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});
            bool hor = ni == x[i];
            if (!hor) all_vert.push_back({x[i], y[i], ni, nj});
            else all_hor.push_back({x[i], y[i], ni, nj});
        }
    }

    for (int z = 0; z < 10; ++z) {
        random_shuffle(all_hor.begin(), all_hor.end());
        random_shuffle(all_vert.begin(), all_vert.end());
        vertical.clear();
        horizontal.clear();
        DSU d;

        auto add_vert = [&] (int vert_ind) -> void {
            const edge& e = all_vert[vert_ind];
            int id1 = vid[{e.i1, e.j1}];
            int id2 = vid[{e.i2, e.j2}];
            if (d.get(id1) == d.get(id2)) return;
            d.merge(id1, id2);
            vertical.push_back(e);
        };

        auto add_hor = [&] (int hor_ind) -> void {
            const edge& e = all_hor[hor_ind];
            int id1 = vid[{e.i1, e.j1}];
            int id2 = vid[{e.i2, e.j2}];
            if (d.get(id1) == d.get(id2)) return;
            d.merge(id1, id2);
            horizontal.push_back(e);
        };

        int vptr = 0;
        int hptr = 0;

        for (int i = 0; i < edges.size(); ++i) {
            if (vptr == all_vert.size()) {
                add_hor(hptr++);
                continue;
            }
            if (hptr == all_hor.size()) {
                add_vert(vptr++);
                continue;
            }
            int r = rand() % 4;
            if (r != 0) {
                add_vert(vptr++);
            }
            else {
                add_hor(hptr++);
            }
        }

        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; 
        });
        int j = try_build();
        if (j == 1) return true;
    }
    return false;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:174:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         for (int i = 0; i < edges.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
parks.cpp:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |             if (vptr == all_vert.size()) {
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
parks.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             if (hptr == all_hor.size()) {
      |                 ~~~~~^~~~~~~~~~~~~~~~~

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 281 ms 31972 KB Output is correct
10 Correct 18 ms 5080 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 29 ms 6368 KB Output is correct
13 Correct 36 ms 8240 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 265 ms 32040 KB Output is correct

Subtask #2
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 281 ms 31972 KB Output is correct
10 Correct 18 ms 5080 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 29 ms 6368 KB Output is correct
13 Correct 36 ms 8240 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 265 ms 32040 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1884 KB Output is correct
21 Correct 2 ms 1884 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Incorrect 2305 ms 38484 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

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 281 ms 31972 KB Output is correct
10 Correct 18 ms 5080 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 29 ms 6368 KB Output is correct
13 Correct 36 ms 8240 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 265 ms 32040 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1884 KB Output is correct
21 Correct 2 ms 1884 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Incorrect 2305 ms 38484 KB Solution announced impossible, but it is possible.
24 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 281 ms 31972 KB Output is correct
10 Correct 18 ms 5080 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 29 ms 6368 KB Output is correct
13 Correct 36 ms 8240 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 265 ms 32040 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 609 ms 66336 KB Output is correct
21 Correct 592 ms 63832 KB Output is correct
22 Correct 592 ms 66576 KB Output is correct
23 Correct 418 ms 55528 KB Output is correct
24 Correct 156 ms 17644 KB Output is correct
25 Correct 328 ms 31136 KB Output is correct
26 Correct 287 ms 33376 KB Output is correct
27 Correct 652 ms 62256 KB Output is correct
28 Correct 626 ms 62004 KB Output is correct
29 Correct 559 ms 63288 KB Output is correct
30 Correct 563 ms 62312 KB Output is correct
31 Correct 1 ms 1880 KB Output is correct
32 Correct 28 ms 6432 KB Output is correct
33 Correct 70 ms 9812 KB Output is correct
34 Correct 575 ms 64160 KB Output is correct
35 Correct 10 ms 3232 KB Output is correct
36 Correct 59 ms 8628 KB Output is correct
37 Correct 137 ms 15416 KB Output is correct
38 Incorrect 580 ms 15036 KB Solution announced impossible, but it is possible.
39 Halted 0 ms 0 KB -

Subtask #5
20.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 281 ms 31972 KB Output is correct
10 Correct 18 ms 5080 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 29 ms 6368 KB Output is correct
13 Correct 36 ms 8240 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 265 ms 32040 KB Output is correct
17 Correct 550 ms 63744 KB Output is correct
18 Correct 573 ms 65428 KB Output is correct
19 Correct 622 ms 63840 KB Output is correct
20 Correct 652 ms 63444 KB Output is correct
21 Correct 523 ms 56632 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Correct 79 ms 11816 KB Output is correct
24 Correct 22 ms 4684 KB Output is correct
25 Correct 93 ms 11728 KB Output is correct
26 Correct 179 ms 19888 KB Output is correct
27 Correct 426 ms 33472 KB Output is correct
28 Correct 460 ms 41352 KB Output is correct
29 Correct 936 ms 50840 KB Output is correct
30 Correct 1240 ms 57428 KB Output is correct
31 Correct 822 ms 65080 KB Output is correct
32 Correct 666 ms 64708 KB Output is correct
33 Correct 677 ms 62644 KB Output is correct
34 Correct 6 ms 2648 KB Output is correct
35 Correct 14 ms 3232 KB Output is correct
36 Correct 297 ms 32424 KB Output is correct
37 Correct 530 ms 49492 KB Output is correct
38 Correct 785 ms 63368 KB Output is correct

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 281 ms 31972 KB Output is correct
10 Correct 18 ms 5080 KB Output is correct
11 Correct 121 ms 18084 KB Output is correct
12 Correct 29 ms 6368 KB Output is correct
13 Correct 36 ms 8240 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 265 ms 32040 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1884 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1884 KB Output is correct
21 Correct 2 ms 1884 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Incorrect 2305 ms 38484 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -