Submission #939208

#TimeUsernameProblemLanguageResultExecution timeMemory
939208WanWanSoccer Stadium (IOI23_soccer)C++17
2 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) #endif const int MAXN = 2005; const int inf=1000000500ll; const long long oo =1000000000000000500ll; const int MOD = (int)1e9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int,int> pi; vector<int> row[MAXN], col[MAXN]; struct ufds_{ int p[MAXN]; ufds_(){ iota(p,p+MAXN,0); } int find(int x){ if(x==p[x])return x; else return p[x]=find(p[x]); } void merge(int x, int y){ x=find(x);y=find(y); p[y]=x; } }ufds; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; int n; int get(int x, int y){ return x*n+y; } int biggest_stadium(int N, std::vector<std::vector<int>> V) { n=N; int cnt=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(V[i][j] == 0){ ++cnt; for(int k=0;k<3;k++){ int nx=i+dx[k]; int ny=j+dy[k]; if(nx<0 || nx>=n ||ny<0 || ny>=n || V[nx][ny])continue; ufds.merge(get(i,j),get(nx,ny)); } } } } unordered_set<int>os; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(V[i][j] == 0)os.insert(ufds.find(get(i,j))); } } if(os.size() > 1)return 0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(V[i][j])row[i].push_back(j); } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(V[i][j])col[j].push_back(i); } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(V[i][j] == 0){ if(upper_bound(row[i].begin(),row[i].end(),j) != row[i].end() && upper_bound(col[j].begin(),col[j].end(),i) != col[j].end()){ int nx=*upper_bound(row[i].begin(),row[i].end(),j); int ny=*upper_bound(col[j].begin(),col[j].end(),i); if(V[nx][ny] == 0)return 0; } if(upper_bound(row[i].begin(),row[i].end(),j) != row[i].end() && lower_bound(col[j].begin(),col[j].end(),i) != col[j].begin()){ int nx=*upper_bound(row[i].begin(),row[i].end(),j); int ny=*prev(lower_bound(col[j].begin(),col[j].end(),i)); if(V[nx][ny] == 0)return 0; } if(lower_bound(row[i].begin(),row[i].end(),j) != row[i].begin() && upper_bound(col[j].begin(),col[j].end(),i) != col[j].end()){ int nx=*prev(lower_bound(row[i].begin(),row[i].end(),j)); int ny=*upper_bound(col[j].begin(),col[j].end(),i); if(V[nx][ny] == 0)return 0; } if(lower_bound(row[i].begin(),row[i].end(),j) != row[i].begin() && lower_bound(col[j].begin(),col[j].end(),i) != col[j].begin()){ int nx=*prev(lower_bound(row[i].begin(),row[i].end(),j)); int ny=*prev(lower_bound(col[j].begin(),col[j].end(),i)); if(V[nx][ny] == 0)return 0; } } } } return cnt; }
#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...