Submission #1232183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232183		alterio	Soccer Stadium (IOI23_soccer)	C++20	1.50 / 100	283 ms	63036 KiB

soccer

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

using namespace std;

const int mxn = 2010;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int ldr[mxn * mxn], rnk[mxn * mxn];
int N;

int F(int x, int y) {
    return x * N + y;
}

int Find(int x) {
    if (ldr[x] == x) return x;
    return ldr[x] = Find(ldr[x]);
}

void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (rnk[y] > rnk[x]) swap(x, y);
    ldr[y] = x;
    rnk[x] += rnk[y];
}

int biggest_stadium(int _N, vector<vector<int>> V) {
    N = _N;
    for (int i = 0; i < N * N; i++) ldr[i] = i, rnk[i] = 1;
    int highest[N], lowest[N];
    for (int i = 0; i < N; i++) highest[i] = N + 1, lowest[i] = -1;
    
    auto valid = [&] (int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    };

    int SZ = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (V[i][j]) continue;
            SZ++;
            for (int d = 0; d < 4; d++) {
                int nx = i + dx[d], ny = j + dy[d];
                if (!valid(nx, ny) || V[nx][ny]) continue;
                Union(F(i, j), F(nx, ny));
            }
        }
    }
    set<int> s;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (V[i][j]) continue;
            s.insert(Find(F(i, j)));
        }
    }
    if (s.size() > 1 || !s.size()) return 0;
    for (int j = 0; j < N; j++) {
        bool flag = 0, obst = 0;
        for (int i = 0; i < N; i++) {
            if (V[i][j]) {
                if (flag) obst = 1;
                continue;
            }
            if (obst) return 0;
            highest[j] = min(highest[j], i);
            lowest[j] = max(lowest[j], i);
            flag = 1;
        }
    } 
    for (int j = 0; j < N; j++) {
        if (highest[j] == N + 1) continue;
        pair<int, int> p = {highest[j], lowest[j]};
        j++;
        while (j < N && p == make_pair(highest[j], lowest[j])) j++;
        if (j == N || highest[j] == N + 1) return SZ;
        pair<int, int> newP = {highest[j], lowest[j]};
        if (newP.first != p.first && newP.second != p.second) return 0;
        j++;
        while (j < N && newP == make_pair(highest[j], lowest[j])) j++;
        if (j == N || highest[j] == N + 1) return SZ;
        return 0;
    }
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^

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