Submission #606127

#	Time	Username	Problem	Language	Result	Execution time	Memory
606127		KoD	Fountain Parks (IOI21_parks)	C++17	45 / 100	1793 ms	70752 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

template <class F>
struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

struct UnionFind {
    vector<int> data;
    explicit UnionFind(const int n) : data(n, -1) {}
    int find(const int u) {
        return data[u] < 0 ? u : data[u] = find(data[u]);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }
};

struct Points {
    vector<pair<int, int>> pts;
    std::map<pair<int, int>, int> map;

    Points() : pts(), map() {}

    int add_or_get(const pair<int, int>& p) {
        if (const auto itr = map.find(p); itr != map.end()) {
            return itr->second;
        } else {
            pts.push_back(p);
            return map[p] = (int)pts.size() - 1;
        }
    }

    int try_get(const pair<int, int>& p) const {
        if (const auto itr = map.find(p); itr != map.end()) {
            return itr->second;
        } else {
            return -1;
        }
    }
};

int construct_roads(vector<int> X, vector<int> Y) {
    const int F = (int)X.size();    
    Points fountain, road, bench;
    for (int i = 0; i < F; ++i) {
        fountain.add_or_get({X[i], Y[i]});
    }
    vector<pair<int, int>> edges;
    for (int i = 0; i < F; ++i) {
        if (const int j = fountain.try_get({X[i] + 2, Y[i]}); j != -1) {
            const int r = road.add_or_get({X[i] + 1, Y[i]});
            if ((X[i] + Y[i]) % 4 == 0) {
                const int b = bench.add_or_get({X[i] + 1, Y[i] + 1});
                edges.emplace_back(r, b);
            } else {
                const int b = bench.add_or_get({X[i] + 1, Y[i] - 1});
                edges.emplace_back(r, b);
            }
        }
        if (const int j = fountain.try_get({X[i], Y[i] + 2}); j != -1) {
            const int r = road.add_or_get({X[i], Y[i] + 1});
            if ((X[i] + Y[i]) % 4 == 0) {
                const int b = bench.add_or_get({X[i] - 1, Y[i] + 1});
                edges.emplace_back(r, b);
            } else {
                const int b = bench.add_or_get({X[i] + 1, Y[i] + 1});
                edges.emplace_back(r, b);
            }
        }
    }
    const int R = (int)road.pts.size();
    const int B = (int)bench.pts.size();
    vector<int> type(B), deg(B);
    for (const auto& [r, b] : edges) {
        deg[b] += 1;
    }
    for (int i = 0; i < B; ++i) {
        const auto& [x, y] = bench.pts[i];
        type[i] = (x / 2 + y / 2) / 2;
    }
    vector<char> use(R, true), visited(B);
    const auto dfs = fixed([&](auto&& dfs, const int r, const int b) -> void {
        if (r == -1 or b == -1 or deg[b] != 2 or visited[b]) {
            return;
        }
        use[r] = false;
        visited[b] = true;
        const auto& [x, y] = bench.pts[b];
        if (type[b] == 0) {
            dfs(road.try_get({x, y - 1}), bench.try_get({x, y - 2}));
            dfs(road.try_get({x, y + 1}), bench.try_get({x, y + 2}));
        } else {
            dfs(road.try_get({x - 1, y}), bench.try_get({x - 2, y}));
            dfs(road.try_get({x + 1, y}), bench.try_get({x + 2, y}));
        }
    });
    for (int src = 0; src < B; ++src) {
        if (deg[src] == 1) {
            const auto& [x, y] = bench.pts[src];
            if (type[src] == 0) {
                dfs(road.try_get({x, y - 1}), bench.try_get({x, y - 2}));
                dfs(road.try_get({x, y + 1}), bench.try_get({x, y + 2}));
            } else {
                dfs(road.try_get({x - 1, y}), bench.try_get({x - 2, y}));
                dfs(road.try_get({x + 1, y}), bench.try_get({x + 2, y}));
            }
        }
    }
    vector<int> match(R);
    for (const auto& [r, b] : edges) {
        if (use[r]) {
            match[r] = b;
        }
    }
    UnionFind dsu(F);
    vector<int> u, v, a, b;
    for (int i = 0; i < R; ++i) {
        const auto& [x, y] = road.pts[i];
        if (x % 2 == 1) {
            const int s = fountain.try_get({x - 1, y});
            const int t = fountain.try_get({x + 1, y});
            if (dsu.merge(s, t)) {
                u.push_back(s);
                v.push_back(t);
                a.push_back(bench.pts[match[i]].first);
                b.push_back(bench.pts[match[i]].second);
            }
        } else {
            const int s = fountain.try_get({x, y - 1});
            const int t = fountain.try_get({x, y + 1});
            if (dsu.merge(s, t)) {
                u.push_back(s);
                v.push_back(t);
                a.push_back(bench.pts[match[i]].first);
                b.push_back(bench.pts[match[i]].second);
            }
        }
    }
    if ((int)u.size() < F - 1) {
        return 0;
    }
    build(u, v, a, b); 
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30