제출 #435237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435237		ecnerwala	분수 공원 (IOI21_parks)	C++17	100 / 100	226 ms	17600 KiB

parks

#include "parks.h"

#include <bits/stdc++.h>

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    int N = int(X.size());
    struct pt_t {
        int x, y, idx;
    };

    std::vector<pt_t> pts(N);
    for (int i = 0; i < N; i++) pts[i] = {X[i], Y[i], i};

    std::vector<int> north(N, -1);
    std::vector<int> east(N, -1);

    std::vector<int> par(N, -1);
    auto get_par = [&](int a) -> int {
        while (par[a] >= 0) {
            if (par[par[a]] >= 0) par[a] = par[par[a]];
            a = par[a];
        }
        return a;
    };
    auto merge = [&](int a, int b) -> bool {
        a = get_par(a), b = get_par(b);
        if (a == b) return false;
        if (par[a] > par[b]) std::swap(a, b);
        par[a] += par[b];
        par[b] = a;
        return true;
    };

    std::sort(pts.begin(), pts.end(), [](pt_t a, pt_t b) { return std::tie(a.x, a.y) < std::tie(b.x, b.y); });
    for (int i = 0; i+1 < N; i++) {
        if (pts[i].x == pts[i+1].x && pts[i].y + 2 == pts[i+1].y) {
            north[pts[i].idx] = pts[i+1].idx;
        }
    }

    std::sort(pts.begin(), pts.end(), [](pt_t a, pt_t b) { return std::tie(a.y, a.x) < std::tie(b.y, b.x); });
    for (int i = 0; i+1 < N; i++) {
        if (pts[i].y == pts[i+1].y && pts[i].x + 2 == pts[i+1].x) {
            east[pts[i].idx] = pts[i+1].idx;
        }
    }

    std::vector<int> U, V, A, B; U.reserve(N-1), V.reserve(N-1), A.reserve(N-1), B.reserve(N-1);

    for (int i = 0; i < N; i++) {
        bool is_full = east[i] != -1 && north[i] != -1 && north[east[i]] != -1;

        if (east[i] != -1) {
            if ((X[i]^Y[i])&2) {
                // We use below us
                if (merge(i, east[i])) {
                    U.push_back(i);
                    V.push_back(east[i]);
                    A.push_back(X[i]+1);
                    B.push_back(Y[i]-1);
                }
            } else {
                // We use above of us, and we're not preferred
                if (!is_full) {
                    if (merge(i, east[i])) {
                        U.push_back(i);
                        V.push_back(east[i]);
                        A.push_back(X[i]+1);
                        B.push_back(Y[i]+1);
                    }
                }
            }
        }
        if (north[i] != -1) {
            if ((X[i]^Y[i])&2) {
                // We use right of us, and we're not preferred
                if (!is_full) {
                    if (merge(i, north[i])) {
                        U.push_back(i);
                        V.push_back(north[i]);
                        A.push_back(X[i]+1);
                        B.push_back(Y[i]+1);
                    }
                }
            } else {
                // We use left of us
                if (merge(i, north[i])) {
                    U.push_back(i);
                    V.push_back(north[i]);
                    A.push_back(X[i]-1);
                    B.push_back(Y[i]+1);
                }
            }
        }
    }

    if (int(U.size()) != N-1) return false;
    build(U, V, A, B); return true;
}

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