Submission #932624

#	Time	Username	Problem	Language	Result	Execution time	Memory
932624		Programmer123	Fountain Parks (IOI21_parks)	C++17	5 / 100	216 ms	54624 KiB

parks

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

std::unordered_map<int, int> map[200001];
int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = (int) x.size();
    if (N == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> u, v, a, b;
    for (int i = 0; i < N; ++i) {
        map[x[i]][y[i]] = i;
    }
    bool seen[N];
    for (int i = 0; i < N; ++i) {
        seen[i] = false;
    }
    std::queue<int> bfs;
    bfs.push(0);
    seen[0] = true;
    auto add = [&](int x, int y, std::vector<int> &data) {
        if (x < 0 || x > 200000) return;
        if (map[x].count(y)) data.push_back(map[x][y]);
    };
    auto edges = [&](int x, int y) {
        std::vector<int> result;
        add(x, y + 2, result);
        add(x, y - 2, result);
        add(x + 2, y, result);
        add(x - 2, y, result);
        return result;
    };
    int rem = N - 1;
    while (!bfs.empty()) {
        auto next = bfs.front();
        bfs.pop();
        for (auto n: edges(x[next], y[next])) {
            if (!seen[n]) {
                seen[n] = true;
                bfs.push(n);
                rem--;
                u.push_back(next);
                v.push_back(n);
            }
        }
    }
    if (rem)
        return 0;

    std::function<std::vector<std::pair<int, int>>(int, int)> valid = [&x, &y](int u,
                                                                               int v) -> std::vector<std::pair<int, int>> {
        if (x[u] == x[v]) {
            int _y = (y[u] + y[v]) / 2;
            return {{x[u] + 1, _y},
                    {x[u] - 1, _y}};
        } else {
            int _x = (x[u] + x[v]) / 2;
            return {{_x, y[u] + 1}, {_x, y[u] - 1}};
        }
    };
    std::vector<std::pair<int, int>> vld[N - 1];
    for (int i = 0; i < N - 1; ++i) {
        vld[i] = valid(u[i], v[i]);
        a.push_back(vld[i][0].first);
        b.push_back(vld[i][0].second);
    }
    build(u, v, a, b);
    return 1;
}

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