제출 #1084827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084827		kilkuwu	Jobs (BOI24_jobs)	C++17	0 / 100	36 ms	4956 KiB

Main

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

#define nl '\n'

struct DSU {
  std::vector<int> e;
  int comp;

  DSU(int n) : e(n, -1), comp(n) {}

  int find(int u) {
    return e[u] < 0 ? u : e[u] = find(e[u]);
  }

  bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    comp--;
    if (e[u] > e[v]) std::swap(u, v);
    e[u] += e[v];
    e[v] = u;
    return true;
  }

  bool same(int u, int v) {
    return find(u) == find(v);
  }

  int size(int u) {
    return -e[find(u)];
  }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    if (N <= 2) {
        std::cout << -1 << nl;
        return 0;
    }

    std::vector<std::pair<int, int>> pos(N);
    int min_x = 1e9, min_y = 1e9;
    int max_x = -1e9, max_y = -1e9;
    for (int i = 0; i < N; i++) {
        std::cin >> pos[i].first >> pos[i].second;
        min_x = std::min(min_x, pos[i].first);
        min_y = std::min(min_y, pos[i].second);
        max_x = std::max(max_x, pos[i].first);
        max_y = std::max(max_y, pos[i].second);
    }

    auto pos2 = pos;


    for (int i = 0; i < N; i++) {
        pos[i].first -= min_x;
        pos[i].second -= min_y;
        pos2[i].first -= max_x;
        pos2[i].second -= max_y;
    }

    std::sort(pos.begin(), pos.end());

    int same_x = 1;
    int same_y = 1;
    for (int i = 1; i < N; i++) {
        same_x &= pos[i].first == pos[0].first;
        same_y &= pos[i].second == pos[0].second;
    }

    if (same_x || same_y) {
        std::cout << -1 << nl;
        return 0;
    }


    DSU dsu(401 * 401);

    auto id = [&](int x, int y) {
        return x * 401 + y;
    };

    for (int x = 0; x < 401; x++) {
        for (int y = 0; y < 401; y++) {
            std::vector<int> inside;
            for (int i = 0; i < N; i++) {
                if (x + pos[i].first < 401 && y + pos[i].second < 401) {
                    inside.push_back(id(x + pos[i].first, y + pos[i].second));
                }
            }
            for (int i = 1; i < (int) inside.size(); i++) {
                dsu.merge(inside[0], inside[i]);
            }
            inside.clear();

            for (int i = 0; i < N; i++) {
                if (x + pos2[i].first >= 0 && y + pos2[i].second >= 0) {
                    inside.push_back(id(x + pos2[i].first, y + pos2[i].second));
                }
            }

            for (int i = 1; i < (int) inside.size(); i++) {
                dsu.merge(inside[0], inside[i]);
            }
        }
    }

    std::cout << dsu.comp << nl;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31