Submission #840893

#	Time	Username	Problem	Language	Result	Execution time	Memory
840893		7mody	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	4555 ms	696 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<int>> row;
vector<vector<int>> col;
vector<vector<int>> arr;
int n;

bool check(int x1,int y1,int x2,int y2){
    if(x1==x2) return (row[x1][y1] - row[x2][y2] == 0);
    if(y1==y2) return (col[x1][y1] - col[x2][y2] == 0);
    return ((row[x1][y1] - row[x1][y2] == 0 && col[x1][y2] - col[x2][y2] == 0) || (col[x1][y1] - col[x2][y1] == 0 && row[x2][y1] - row[x2][y2] == 0));
}

int biggest_stadium(int N, vector<vector<int>> F)
{
    arr=F;
    n=N;
    int ans=0;
    row=F;
    col=F;
    for(int i=0; i < n;i++){
        for(int j=1; j < n;j++){
            row[i][j]+=row[i][j-1];
            col[j][i]+=col[j-1][i];
        }
    }

    // for(auto c  : row){
    //     for(auto g : c){
    //         cout << g << ' ';
    //     }
    //     cout << endl;
    // }

    // for(auto c  : col){
    //     for(auto g : c){
    //         cout << g << ' ';
    //     }
    //     cout << endl;
    // }

    queue<pair<int,int>> q;

    for(int i=0; i < n;i++){
        for(int j=0; j < n;j++){
            int curr=1;
            if(!arr[i][j]){
                q.push({i+1,j});
                q.push({i,j+1});
                q.push({i-1,j});
                q.push({i,j-1});
            }
            vector<pair<int,int>> found;
            vector<vector<bool>> vis(n,vector<bool>(n));
            vis[i][j]=true;
            found.push_back({i,j});
            while(!q.empty()){
                int x=q.front().first,y=q.front().second;
                q.pop();
                bool ok=true;
                if(x==-1 || x==n || y==-1 || y==n || arr[x][y] || vis[x][y]) continue;
                for(pair<int,int> c : found){
                    if(!check(c.first,c.second, x , y)){
                        ok=false;
                        break;
                    }
                }
                if(!ok) continue;
                vis[x][y]=true;
                found.push_back({x,y});
                curr++;
                // cout << curr << ' ' << x << ' ' << y << endl;
                q.push({x+1,y});
                q.push({x,y+1});
                q.push({x-1,y});
                q.push({x,y-1});
            }
            ans=max(ans,curr);
        }
    }
    return ans;
}

// void solve(){
//     int n; cin >> n;
//     vector<vector<int>> arr(n,vector<int>(n));
//     for(int i=0; i < n;i++){
//         for(int j=0; j < n;j++){
//             cin >> arr[i][j];
//         }
//     }
//     cout << biggest_stadium(n,arr) << endl;
// }


// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie();
//     cout.tie();
//     int t=1;
//     cin >> t;
//     while(t--){
//         solve();
//     }
// }

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30