oj.uz

Submission #1084830

# Submission time Handle Problem Language Result Execution time Memory
1084830 2024-09-07T04:44:48 Z kilkuwu Portal (BOI24_portal) C++17
1 / 100
 2000 ms 4004 KB 
#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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 456 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 388 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 456 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Incorrect 4 ms 856 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 2093 ms 4004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 860 KB Output is correct
2 Correct 16 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 141 ms 860 KB Output is correct
5 Correct 116 ms 856 KB Output is correct
6 Correct 114 ms 856 KB Output is correct
7 Correct 132 ms 860 KB Output is correct
8 Correct 122 ms 856 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 21 ms 972 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 456 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Incorrect 4 ms 856 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 456 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 12 ms 860 KB Output is correct
20 Incorrect 4 ms 856 KB Output isn't correct
21 Halted 0 ms 0 KB -