oj.uz

Submission #1061748

# Submission time Handle Problem Language Result Execution time Memory
1061748 2024-08-16T12:36:12 Z mc061 Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 66404 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 < 20; ++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() % 2;
            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 1752 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 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 273 ms 32056 KB Output is correct
10 Correct 17 ms 4948 KB Output is correct
11 Correct 120 ms 17976 KB Output is correct
12 Correct 30 ms 6376 KB Output is correct
13 Correct 38 ms 8252 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 250 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 1752 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 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 273 ms 32056 KB Output is correct
10 Correct 17 ms 4948 KB Output is correct
11 Correct 120 ms 17976 KB Output is correct
12 Correct 30 ms 6376 KB Output is correct
13 Correct 38 ms 8252 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 250 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 1880 KB Output is correct
21 Correct 1 ms 1884 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Execution timed out 3601 ms 39528 KB Time limit exceeded
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 1752 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 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 273 ms 32056 KB Output is correct
10 Correct 17 ms 4948 KB Output is correct
11 Correct 120 ms 17976 KB Output is correct
12 Correct 30 ms 6376 KB Output is correct
13 Correct 38 ms 8252 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 250 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 1880 KB Output is correct
21 Correct 1 ms 1884 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Execution timed out 3601 ms 39528 KB Time limit exceeded
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 1752 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 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 273 ms 32056 KB Output is correct
10 Correct 17 ms 4948 KB Output is correct
11 Correct 120 ms 17976 KB Output is correct
12 Correct 30 ms 6376 KB Output is correct
13 Correct 38 ms 8252 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 250 ms 32040 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 629 ms 66256 KB Output is correct
21 Correct 558 ms 64044 KB Output is correct
22 Correct 592 ms 65428 KB Output is correct
23 Correct 458 ms 55608 KB Output is correct
24 Correct 161 ms 17536 KB Output is correct
25 Correct 315 ms 31544 KB Output is correct
26 Correct 256 ms 31144 KB Output is correct
27 Correct 628 ms 62244 KB Output is correct
28 Correct 658 ms 62168 KB Output is correct
29 Correct 588 ms 63808 KB Output is correct
30 Correct 582 ms 62532 KB Output is correct
31 Correct 1 ms 1884 KB Output is correct
32 Correct 29 ms 6388 KB Output is correct
33 Correct 78 ms 9808 KB Output is correct
34 Correct 587 ms 64600 KB Output is correct
35 Correct 10 ms 3232 KB Output is correct
36 Correct 61 ms 8852 KB Output is correct
37 Correct 135 ms 15928 KB Output is correct
38 Incorrect 1085 ms 15000 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 1752 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 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 273 ms 32056 KB Output is correct
10 Correct 17 ms 4948 KB Output is correct
11 Correct 120 ms 17976 KB Output is correct
12 Correct 30 ms 6376 KB Output is correct
13 Correct 38 ms 8252 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 250 ms 32040 KB Output is correct
17 Correct 548 ms 63640 KB Output is correct
18 Correct 531 ms 66404 KB Output is correct
19 Correct 582 ms 64004 KB Output is correct
20 Correct 627 ms 63664 KB Output is correct
21 Correct 512 ms 56560 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Correct 165 ms 11832 KB Output is correct
24 Correct 22 ms 4944 KB Output is correct
25 Correct 93 ms 12552 KB Output is correct
26 Correct 175 ms 19888 KB Output is correct
27 Incorrect 1651 ms 20092 KB Solution announced impossible, but it is possible.
28 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 1752 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 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 273 ms 32056 KB Output is correct
10 Correct 17 ms 4948 KB Output is correct
11 Correct 120 ms 17976 KB Output is correct
12 Correct 30 ms 6376 KB Output is correct
13 Correct 38 ms 8252 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2140 KB Output is correct
16 Correct 250 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 1880 KB Output is correct
21 Correct 1 ms 1884 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct
23 Execution timed out 3601 ms 39528 KB Time limit exceeded
24 Halted 0 ms 0 KB -