Submission #1059656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059656		mychecksedad	Soccer Stadium (IOI23_soccer)	C++17	1.50 / 100	301 ms	71560 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 200005;

int arr[4][2]={
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0}
};
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
  vector<vector<int>> U(n, vector<int>(n));
  vector<vector<int>> L(n, vector<int>(n));
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(i == 0){
        if(a[i][j] == 1) U[i][j] = i;
        else U[i][j] = -1;
      }else{
        if(a[i][j] == 1){
          if(a[i - 1][j] == 1) U[i][j] = U[i - 1][j];
          else U[i][j] = i;
        }else{
          U[i][j] = -1;
        }
      }
      if(j == 0){
        if(a[i][j] == 1) L[i][j] = j;
        else U[i][j] = -1;
      }else{
        if(a[i][j] == 1){
          if(a[i][j - 1] == 1) L[i][j] = L[i][j - 1];
          else L[i][j] = j;
        }else{
          L[i][j] = -1;
        }
      }
    }
  }
  queue<pair<int, int>> q;
  vector<vector<bool>> vis(n, vector<bool>(n));
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i][j] == 0){
        q.push({i, j});
        vis[i][j] = 1;
        break;
      }
    }
    if(q.size()) break;
  }
  int sz = 0;
  while(!q.empty()){
    int x = q.front().ff;
    int y = q.front().ss;
    q.pop();
    for(int i = 0; i < 4; ++i){
      int nx = x + arr[i][0];
      int ny = y + arr[i][1];
      if(nx >= 0 && ny >= 0 && nx < n && ny < n && !vis[nx][ny] && a[nx][ny] == 0){
        vis[nx][ny] = 1;
        q.push({nx, ny});
      }
    }
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i][j] == 0 && vis[i][j] == 0){
        return false;
      }
      if(a[i][j] == 1) continue;
      ++sz;
      if(i > 0){
        if(a[i - 1][j] == 1){
          int pos = U[i - 1][j];
          if(pos > 0 && a[pos - 1][j] == 0){
            return false;
          }
        }
      }
      if(j > 0){
        if(a[i][j - 1] == 1){
          int pos = L[i][j - 1];
          if(pos > 0 && a[i][pos - 1] == 0){
            return false;
          }
        }
      }
    }
  }

  return sz;
}

• 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