Submission #1240590

#TimeUsernameProblemLanguageResultExecution timeMemory
1240590mychecksedadSoccer Stadium (IOI23_soccer)C++17
25 / 100
707 ms314664 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define pii pair<int,int> #define ff first #define ss second #define ll long long int #define cerr if(0) cerr const int N = 2005, M = 3e5; int arr[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; bitset<N> vis[N]; vector<pii> g[N][N]; int biggest_stadium(int n, std::vector<std::vector<int>> a) { queue<pii> q; bool any = false; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(a[i][j] == 0){ if(!any){ any = true; q.push({i, j}); vis[i][j] = 1; } for(int k = 0; k < 4; ++k){ int nx = i + arr[k][0]; int ny = j + arr[k][1]; if(nx >= 0 && ny < n && ny >= 0 && nx < n && a[nx][ny] == 0){ g[i][j].pb({nx, ny}); } } } } } int sz = 0; while(!q.empty()){ int x = q.front().ff; int y = q.front().ss; q.pop(); ++sz; for(auto [ux, uy]: g[x][y]){ if(!vis[ux][uy]){ vis[ux][uy] = 1; q.push({ux, uy}); } } } for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(!vis[i][j] && !a[i][j]){ return 0; } } } vector<pii> R; for(int i = 0; i < n; ++i){ int l = n, r = -2; for(int j = 0; j < n; ++j){ if(!a[i][j]) l = min(l, j); if(!a[i][j]){ if(r != -2 && r < j - 1) return 0; r = max(r, j); } } if(l < n){ R.pb({l, r}); } } for(int i = 0; i < n; ++i){ int l = n, r = -2; for(int j = 0; j < n; ++j){ if(!a[j][i]) l = min(l, j); if(!a[j][i]){ if(r != -2 && r < j - 1) return 0; r = max(r, j); } } } for(auto [lx, rx]: R){ for(auto [ly, ry]: R){ if(lx <= ly && ry <= rx) continue; if(ly <= lx && rx <= ry) continue; 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...