Submission #839921

#TimeUsernameProblemLanguageResultExecution timeMemory
839921abdzagSoccer Stadium (IOI23_soccer)C++17
1.50 / 100
549 ms345304 KiB
#include "soccer.h" #include <bits/stdc++.h> typedef long long ll; const long long inf = 2e9; using namespace std; vector<ll> dr = {1, -1, 0, 0}; vector<ll> dc = {0, 0, 1, -1}; bool inside(ll r, ll c, ll N) { return r >= 0 and c >= 0 and r < N and c < N; } void dfs(ll r, ll c, vector<vector<bool>> &visited, vector<vector<int>> &grid) { if (visited[r][c]) return; visited[r][c] = 1; for (int i = 0; i < 4; i++) { ll next_r = r + dr[i]; ll next_c = c + dc[i]; if (!inside(next_r, next_c, grid.size()) or grid[next_r][next_c]) continue; dfs(next_r, next_c, visited, grid); } } bool ALlConnected(std::vector<std::vector<int>> &F) { ll n = F.size(); vector<vector<bool>> visited(n, vector<bool>(n)); bool done_dfs=0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (F[i][j] == 0 and !visited[i][j]) { if (done_dfs){ return 0; } done_dfs = 1; dfs(i, j, visited, F); } } } return 1; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { ll ans = 0; if (!ALlConnected(F)) return -1; vector<vector<int>> columns(N), rows(N); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if(!F[r][c]){ ans++; continue; } ll counter=0; for (int i = 0; i < 4; i++) { ll next_r = r + dr[i]; ll next_c = c + dc[i]; if (!inside(next_r, next_c, N)) continue; counter+=!F[next_r][next_c]; } if(counter>2)return -1; if(counter==2){ columns[c].push_back(r); rows[r].push_back(c); } } } for(int c=0; c<N; c++){ sort(columns[c].begin(),columns[c].end()); for(int i=0; i<(int)columns[c].size()-1; i++){ if(F[columns[c][i]+1][c]){ return -1; } } } for(int r=0; r<N; r++){ sort(rows[r].begin(),rows[r].end()); for(int i=0; i<(int)rows[r].size()-1; i++){ if(F[r][rows[r][i]+1]){ return -1; } } } return ans; }
#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...