Submission #840879

#TimeUsernameProblemLanguageResultExecution timeMemory
840879YassirSalamaSoccer Stadium (IOI23_soccer)C++17
1.50 / 100
1449 ms429968 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; #define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n"; void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__); #define endl "\n" #define pb push_back #define F first #define S second #define ll long long #define mod 1000000007 #define all(v) v.begin(),v.end() map<pair<int,int>,int> mp; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; vector<vector<int>> v; vector<vector<bool>> visited; bool check(int i,int j){ int n=v.size(); return i>=0&&j>=0&&i<n&&j<n&&!visited[i][j]; } map<int,int> sz; void dfs(int i,int j,int comp){ mp[{i,j}]=comp; sz[comp]++; visited[i][j]=true; for(int x=0;x<4;x++){ int ni=dx[x]+i; int nj=dy[x]+j; if(check(ni,nj)) dfs(ni,nj,comp); } } int biggest_stadium(int n, vector<vector<int>> d) { int ii=-1; v=d; int jj=-1; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(v[i][j]){ ii=i; jj=j; break; } } } if(ii==-1) return n*n; // dbg(ii,jj); int ans=0; vector<vector<bool>> visted(n,vector<bool>(n,0)); visited=visted; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==ii) visited[i][j]=true; if(j==jj) visited[i][j]=true; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ // cout<<visited[i][j]<<" "; } // cout<<endl; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(!visited[i][j]) { if(i>ii){ if(j>jj){ dfs(i,j,3); }else{ dfs(i,j,2); } }else{ if(j>jj){ dfs(i,j,1); }else{ dfs(i,j,0); } } } } } // dbg(sz[0],sz[1],sz[2],sz[3],ii,jj); // dbg(sz[0]+sz[1]+jj, // sz[0]+sz[2]+ii, // sz[1]+sz[3]+n-jj-1, // sz[2]+sz[3]+n-ii-1); if((ii==0&&jj==0)||(ii==n-1&&jj==n-1)||(ii==0&&jj==n-1)||(ii==n-1&&jj==0)) return (n-1)*(n-1)+2*n-2; ans=max({sz[0],sz[1],sz[2],sz[3], sz[0]+sz[1]+ii, sz[0]+sz[2]+jj, sz[1]+sz[3]+n-jj-1, sz[2]+sz[3]+n-ii-1 }); return ans; } #ifdef IOI int main() { int N; assert(1 == scanf("%d", &N)); vector<vector<int>> F(N, vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { assert(1 == scanf("%d", &F[i][j])); } } fclose(stdin); int res = biggest_stadium(N, F); printf("%d\n", res); fclose(stdout); return 0; } #endif
#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...