Submission #1061748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061748		mc061	Fountain Parks (IOI21_parks)	C++17	5 / 100	3601 ms	66404 KiB

parks

#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 (stderr)

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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30