제출 #492522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492522		dxz05	분수 공원 (IOI21_parks)	C++17	5 / 100	552 ms	31452 KiB

parks

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

using namespace std;

const int N = 2e5 + 3e2;

#define all(x) (x).begin(), (x).end()

int p[N];

int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (rand() & 1) swap(x, y);
    p[x] = y;
    return true;
}

bool can(vector<int> &x, vector<int> &y, vector<int> &U, vector<int> &V, vector<int> &A, vector<int> &B, const vector<int> &dx, const vector<int> &dy){
    int n = x.size();

    bool ok = true;
    set<pair<int, int>> points;
    for (int it = 0; it < n - 1; it++){
        A[it] = B[it] = 0;

        int i = U[it], j = V[it];
        int X = (x[i] + x[j]) / 2, Y = (y[i] + y[j]) / 2;
        if (x[i] == x[j]){
            for (int d : dx){
                if (!points.count({x[i] + d, Y})){
                    A[it] = x[i] + d;
                    break;
                }
            }

            B[it] = Y;
        } else {
            for (int d : dy){
                if (!points.count({X, y[i] + d})){
                    B[it] = y[i] + d;
                    break;
                }
            }

            A[it] = X;
        }

        if (A[it] == 0 || B[it] == 0) ok = false;

        points.insert({A[it], B[it]});
    }

    return ok;
}

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    if (n == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    vector<int> perm(n);
    iota(all(perm), 0);
    sort(all(perm), [&](int i, int j){
        return x[i] < x[j] || x[i] == x[j] && y[i] < y[j];
    });

    iota(p, p + n, 0);

    map<pair<int, int>, int> id;
    for (int i = 0; i < n; i++){
        id[{x[i], y[i]}] = i;
    }

    vector<int> U, V, A(n - 1), B(n - 1);

    vector<int> dx = {0, 2};
    vector<int> dy = {2, 0};

    for (int it = 0; it < dx.size(); it++){
        for (int i : perm){
            int X = x[i] + dx[it], Y = y[i] + dy[it];
            if (id.find({X, Y}) != id.end()){
                int j = id[{X, Y}];
                if (!unite(i, j)) continue;
                U.push_back(i);
                V.push_back(j);
            }
        }
    }

    if (U.size() != n - 1) return 0;

    if (can(x, y, U, V, A, B, {1, -1}, {1, -1})){
        build(U, V, A, B);
        return 1;
    }

    if (can(x, y, U, V, A, B, {1, -1}, {-1, 1})){
        build(U, V, A, B);
        return 1;
    }

    if (can(x, y, U, V, A, B, {-1, 1}, {1, -1})){
        build(U, V, A, B);
        return 1;
    }

    if (can(x, y, U, V, A, B, {-1, 1}, {-1, 1})){
        build(U, V, A, B);
        return 1;
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

parks.cpp: In lambda function:
parks.cpp:73:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |         return x[i] < x[j] || x[i] == x[j] && y[i] < y[j];
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int it = 0; it < dx.size(); it++){
      |                      ~~~^~~~~~~~~~~
parks.cpp:100:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     if (U.size() != n - 1) return 0;
      |         ~~~~~~~~~^~~~~~~~

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