제출 #1158566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158566		The_Samurai	축구 경기장 (IOI23_soccer)	C++20	25 / 100	266 ms	63188 KiB

soccer

#include "soccer.h"
#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> p, size;

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

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

    void add(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 biggest_stadium(int n, std::vector<std::vector<int>> a) {
    dsu ds; ds.init(n * n);
    vector<tuple<int, int, int>> ranges;
    // for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
    //     cout << a[i][j];
    //     if (j == n - 1) cout << endl;
    // }
    for (int i = 0; i < n; i++) {
        int j = 0;
        while (j < n and a[i][j]) j++;
        if (j == n) continue;
        ranges.emplace_back(i, j, j);
        while (j < n and !a[i][j]) j++;
        get<2>(ranges.back()) = j - 1;

        // if it contains another range?
        while (j < n and a[i][j]) j++;
        if (j != n) return 0;
    }

    // another check
    for (int j = 0; j < n; j++) {
        int i = 0;
        while (i < n and a[i][j]) i++;
        if (i == n) continue;
        while (i < n and !a[i][j]) i++;
        while (i < n and a[i][j]) i++;
        if (i != n) return 0;
    }

    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    pair<int, int> any;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) continue;
            for (int k = 0; k < 4; k++) {
                auto [x, y] = make_pair(i + dx[k], j + dy[k]);
                if (min(x, y) < 0 or max(x, y) >= n) continue;
                if (!a[x][y]) ds.add(i * n + j, x * n + y);
            }
            any = make_pair(i, j);
        }
    }

    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (!a[i][j] and ds.get(i * n + j) != ds.get(any.first * n + any.second)) {
            return 0;
        }
    }


    int sum = 0;
    for (int p1 = 0; p1 < ranges.size(); p1++) {
        sum += get<2>(ranges[p1]) - get<1>(ranges[p1]) + 1;
        // cout << get<0>(ranges[p1]) << ' ' << get<1>(ranges[p1]) << ' ' << get<2>(ranges[p1]) << endl;
        for (int p2 = 0; p2 < ranges.size(); p2++) {
            auto [i, l, shit1] = ranges[p1];
            auto [j, shit2, r] = ranges[p2];
            bool ok = false;
            ok |= !a[i][r];
            ok |= !a[j][l];
            if (!ok) return 0;
        }
    }
    return sum;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 6
• Subtask 2: 2 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 4 / 16
• Subtask 6: 7.5 / 30