제출 #1241815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241815		The_Samurai	분수 공원 (IOI21_parks)	C++20	100 / 100	467 ms	27236 KiB

parks

#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second

struct dsu {
    vector<int> p, size;
    void init(int n) {
        p.assign(n, 0); size.assign(n, 1);
        for (int i = 0; i < n; i++) p[i] = i;
    }

    int get(int a) {
        return p[a] == a ? a : p[a] = get(p[a]);
    }

    void merge(int a, int b) {
        a = get(a); b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    int n = X.size();
    vector<array<int, 3>> a(n);
    vector<pair<int, int>> all;
    for (int i = 0; i < n; i++) {
        a[i] = array<int, 3>{X[i], Y[i], i};
        all.emplace_back(X[i] - 1, Y[i] - 1);
        all.emplace_back(X[i] - 1, Y[i] + 1);
        all.emplace_back(X[i] + 1, Y[i] - 1);
        all.emplace_back(X[i] + 1, Y[i] + 1);
    }
    sort(a.begin(), a.end());
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());

    auto id = [&](int x, int y) -> int {
        int i = lower_bound(a.begin(), a.end(), array<int, 3>{x, y, 0}) - a.begin();
        if (i == n) return -1;
        return a[i][0] == x and a[i][1] == y ? a[i][2] : -1;
    };

    dsu ds; ds.init(n);
    vector<tuple<int, int, int, int>> ans;
    for (auto [x, y]: all) {
        for (int t = 0; t < 2; t++) {
            if ((x + y) % 4 == t * 2) {
                int i = id(x - 1, y - 1), j = id(x - 1, y + 1);
                if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
                    ds.merge(i, j);
                    ans.emplace_back(x, y, i, j);
                    break;
                }
                i = id(x + 1, y - 1), j = id(x + 1, y + 1);
                if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
                    ds.merge(i, j);
                    ans.emplace_back(x, y, i, j);
                    break;
                }
            } else {
                int i = id(x - 1, y - 1), j = id(x + 1, y - 1);
                if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
                    ds.merge(i, j);
                    ans.emplace_back(x, y, i, j);
                    break;
                }
                i = id(x - 1, y + 1), j = id(x + 1, y + 1);
                if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
                    ds.merge(i, j);
                    ans.emplace_back(x, y, i, j);
                    break;
                }
            }
        }
    }
    bool ok = true;
    for (int i = 1; i < n; i++) ok &= ds.get(i) == ds.get(0);
    if (!ok) return 0;
    vector<int> U, V, A, B;
    for (auto [a, b, u, v]: ans) {
        U.emplace_back(u);
        V.emplace_back(v);
        A.emplace_back(a);
        B.emplace_back(b);
    }
    build(U, V, A, B);
    return 1;
}

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