Submission #1059684

#TimeUsernameProblemLanguageResultExecution timeMemory
1059684mychecksedadSoccer Stadium (IOI23_soccer)C++17
25 / 100
349 ms134932 KiB
#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>> U2(n, vector<int>(n)); vector<vector<int>> L(n, vector<int>(n)); vector<vector<int>> L2(n, vector<int>(n)); vector<vector<int>> R2(n, vector<int>(n)); vector<vector<int>> pref(n, vector<int>(n)); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ pref[i][j] = a[i][j] == 0; if(i > 0) pref[i][j] += pref[i - 1][j]; if(j > 0) pref[i][j] += pref[i][j - 1]; if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1]; 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 L[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; } } if(i == 0){ if(a[i][j] == 0) U2[i][j] = i; else U2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i - 1][j] == 0) U2[i][j] = U2[i - 1][j]; else U2[i][j] = i; }else{ U2[i][j] = -1; } } if(j == 0){ if(a[i][j] == 0) L2[i][j] = j; else L2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i][j - 1] == 0) L2[i][j] = L2[i][j - 1]; else L2[i][j] = j; }else{ L2[i][j] = -1; } } } for(int j = n-1; j >= 0; --j){ if(j == n-1){ if(a[i][j] == 0) R2[i][j] = j; else R2[i][j] = -1; }else{ if(a[i][j] == 0){ if(a[i][j + 1] == 0) R2[i][j] = R2[i][j + 1]; else R2[i][j] = j; }else{ R2[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 0; } 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 0; } } } if(j > 0){ if(a[i][j - 1] == 1){ int pos = L[i][j - 1]; if(pos > 0 && a[i][pos - 1] == 0){ return 0; } } } int lx = L2[i][j]; int rx = R2[i][j]; int dx = U2[i][j]; // dx - 1, lx - 1 // dx - 1, n - 1 / dx - 1, rx if(dx > 0 && lx > 0){ if(pref[dx - 1][lx - 1] > 0) return 0; } if(dx > 0){ if(pref[dx - 1][n - 1] - pref[dx - 1][rx] > 0) return 0; } } } return sz; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...