oj.uz

Submission #1061749

# Submission time Handle Problem Language Result Execution time Memory
1061749 2024-08-16T12:37:16 Z mc061 Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 66832 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() % 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 260 ms 31960 KB Output is correct
10 Correct 18 ms 5084 KB Output is correct
11 Correct 125 ms 17936 KB Output is correct
12 Correct 27 ms 6380 KB Output is correct
13 Correct 38 ms 8360 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 270 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 260 ms 31960 KB Output is correct
10 Correct 18 ms 5084 KB Output is correct
11 Correct 125 ms 17936 KB Output is correct
12 Correct 27 ms 6380 KB Output is correct
13 Correct 38 ms 8360 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 270 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 1 ms 1884 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 42460 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 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 260 ms 31960 KB Output is correct
10 Correct 18 ms 5084 KB Output is correct
11 Correct 125 ms 17936 KB Output is correct
12 Correct 27 ms 6380 KB Output is correct
13 Correct 38 ms 8360 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 270 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 1 ms 1884 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 42460 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 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 260 ms 31960 KB Output is correct
10 Correct 18 ms 5084 KB Output is correct
11 Correct 125 ms 17936 KB Output is correct
12 Correct 27 ms 6380 KB Output is correct
13 Correct 38 ms 8360 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 270 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 2 ms 1880 KB Output is correct
20 Correct 638 ms 66832 KB Output is correct
21 Correct 643 ms 63988 KB Output is correct
22 Correct 576 ms 65428 KB Output is correct
23 Correct 432 ms 54836 KB Output is correct
24 Correct 166 ms 17484 KB Output is correct
25 Correct 333 ms 32684 KB Output is correct
26 Correct 276 ms 30844 KB Output is correct
27 Correct 697 ms 62452 KB Output is correct
28 Correct 691 ms 62160 KB Output is correct
29 Correct 620 ms 63540 KB Output is correct
30 Correct 613 ms 62632 KB Output is correct
31 Correct 1 ms 1880 KB Output is correct
32 Correct 28 ms 6304 KB Output is correct
33 Correct 75 ms 9580 KB Output is correct
34 Correct 602 ms 64440 KB Output is correct
35 Correct 11 ms 3244 KB Output is correct
36 Correct 61 ms 8724 KB Output is correct
37 Correct 144 ms 15468 KB Output is correct
38 Incorrect 1123 ms 15196 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 260 ms 31960 KB Output is correct
10 Correct 18 ms 5084 KB Output is correct
11 Correct 125 ms 17936 KB Output is correct
12 Correct 27 ms 6380 KB Output is correct
13 Correct 38 ms 8360 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 270 ms 32040 KB Output is correct
17 Correct 598 ms 63608 KB Output is correct
18 Correct 606 ms 66412 KB Output is correct
19 Correct 588 ms 63972 KB Output is correct
20 Correct 665 ms 63440 KB Output is correct
21 Correct 571 ms 56628 KB Output is correct
22 Correct 1 ms 1880 KB Output is correct
23 Incorrect 415 ms 7700 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 260 ms 31960 KB Output is correct
10 Correct 18 ms 5084 KB Output is correct
11 Correct 125 ms 17936 KB Output is correct
12 Correct 27 ms 6380 KB Output is correct
13 Correct 38 ms 8360 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 270 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 1 ms 1884 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 42460 KB Time limit exceeded
24 Halted 0 ms 0 KB -