Submission #579216

#	Time	Username	Problem	Language	Result	Execution time	Memory
579216		KoD	Fountain Parks (IOI21_parks)	C++17	30 / 100	460 ms	38824 KiB

parks

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

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

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

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;
    }
};

int construct_roads(vector<int> X, vector<int> Y) {
    const int N = (int)X.size();
    std::map<pair<int, int>, int> map;
    for (int i = 0; i < N; ++i) {
        map[{X[i], Y[i]}] = i;
    }
    UnionFind dsu(N);
    vector<array<int, 4>> edges;

    vector<int> up(N, -1), left(N, -1), right(N, -1);
    
    for (const auto& [p, i] : map) {
        const auto& [x, y] = p;
        const auto itr = map.find(pair(x, y + 2));
        if (itr != map.end()) {
            const int j = itr->second;
            if (!dsu.merge(i, j)) {
                continue;
            }
            if (x == 2) {
                edges.push_back({i, j, x - 1, y + 1});
            } else if (x == 6) {
                edges.push_back({i, j, x + 1, y + 1});
            } else {
                up[i] = (int)edges.size();
                edges.push_back({i, j, -1, -1});
            }
        }
    }

    for (const auto& [p, i] : map) {
        const auto& [x, y] = p;
        const auto itr = map.find(pair(x + 2, y));
        if (itr != map.end()) {
            const int j = itr->second;
            if (!dsu.merge(i, j)) {
                continue;
            }
            if (x == 2) {
                left[j] = (int)edges.size();
                edges.push_back({i, j, -1, -1});
            } else {
                right[i] = (int)edges.size();
                edges.push_back({i, j, -1, -1});
            }
        }
    }

    if ((int)edges.size() != N - 1) {
        return 0;
    }

    std::set<pair<int, int>> used;
    for (const auto& [p, i] : map) {
        if (X[i] != 4) {
            continue;
        }
        if (left[i] != -1) {
            const int x = 3;
            const int y = used.find(pair(x, Y[i] - 1)) != used.end() ? Y[i] + 1 : Y[i] - 1;
            used.emplace(x, y);
            edges[left[i]][2] = x;
            edges[left[i]][3] = y;
        }
        if (right[i] != -1) {
            const int x = 5;
            const int y = used.find(pair(x, Y[i] - 1)) != used.end() ? Y[i] + 1 : Y[i] - 1;
            used.emplace(x, y);
            edges[right[i]][2] = x;
            edges[right[i]][3] = y;
        }
        if (up[i] != -1) {
            const int y = Y[i] + 1;
            const int x = used.find(pair(3, y)) != used.end() ? 5 : 3;
            used.emplace(x, y);
            edges[up[i]][2] = x;
            edges[up[i]][3] = y;
        }
    }

    vector<int> U, V, A, B;
    for (const auto& [u, v, a, b] : edges) {
        U.push_back(u);
        V.push_back(v);
        A.push_back(a);
        B.push_back(b);
    }
    build(U, V, A, B);

    return 1;
}

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