Submission #1132709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132709		SpyrosAliv	Soccer Stadium (IOI23_soccer)	C++20	1.50 / 100	511 ms	317668 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
const int MN = 2005;
int grid[MN][MN], n;
bool a[MN][MN], b[MN][MN], r[MN][MN], l[MN][MN], vis[MN][MN];
 
bool inside(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < n;
}
 
void flood(int i, int j ) {
    vis[i][j] = true;
    for (auto [pi, pj]: delta) {
        int ni = i + pi, nj = j + pj;
        if (inside(ni, nj) && !vis[ni][nj] && grid[ni][nj] == 0) {
            flood(ni, nj);
        }
    }
}
 
int biggest_stadium(int sz, vector<vector<int>> F) {
    n = sz;
    int tot = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            b[i][j] = a[i][j] = r[i][j] = l[i][j] = vis[i][j] = false;
            grid[i][j] = F[i][j];
            if (grid[i][j] == 0) tot++;
        }
    }
    // Case 1: the 0s are disconnected
    bool fin = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1 || vis[i][j]) continue;
            if (fin) return tot - 1; // disconnected
            flood(i, j);
            fin = true;
        }
    }
 
    // Case 2: there both at the right and at the left a 0 for some 1 cell
    // same with above or below
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j > 0 && l[i][j-1]) l[i][j] = true;
            if (grid[i][j] == 0) l[i][j] = true;
        }
        for (int j = n-1; j >= 0; j--) {
            if (j < n-1 && r[i][j+1]) r[i][j] = true;
            if (grid[i][j] == 0) r[i][j] = true;
        }
    }
 
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            if (i > 0 && a[i-1][j]) a[i][j] = true;
            if (grid[i][j] == 0) a[i][j] = true;
        }
        for (int i = n-1; i >= 0; i--) {
            if (i < n-1 && b[i+1][j]) b[i][j] = true;
            if (grid[i][j] == 0) b[i][j] = true;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (b[i][j] && a[i][j] && grid[i][j]) {
                return tot-1;
            }
            if (r[i][j] && l[i][j] && grid[i][j]) {
                return tot-1;
            }
        }
    }
 
    return tot;
}

• 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