Submission #1285172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285172		MMihalev	Soccer Stadium (IOI23_soccer)	C++20	1.50 / 100	386 ms	305788 KiB

soccer

#include<iostream>
#include<vector>
#include<algorithm>
#include "soccer.h"
using namespace std;
const int MAX_N=2e3+3;
int a[MAX_N][MAX_N];
bool tmp[MAX_N][MAX_N];
int n;
bool used[MAX_N][MAX_N];
int dx[]={0,-1,0,+1};
int dy[]={-1,0,+1,0};
void dfs(int i,int j)
{
    used[i][j]=1;
    for(int id=0;id<4;id++)
    {
        int ni=i+dx[id],nj=j+dy[id];
        if(ni<0 or ni>=n or nj<0 or nj>=n)continue;
        if(used[ni][nj] or tmp[ni][nj]==0)continue;
        dfs(ni,nj);
    }
}
bool check()
{
    bool has=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            used[i][j]=0;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!tmp[i][j])continue;
            if(!used[i][j])
            {
                if(has)return 0;
                has=1;
                dfs(i,j);
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(tmp[i][j])continue;
            int cntadjtmp=0;
            int r1=-1,c1=-1;
            for(int id=0;id<4;id++)
            {
                int ni=i+dx[id],nj=j+dy[id];
                if(ni<0 or ni>=n or nj<0 or nj>=n)continue;
                if(tmp[ni][nj]==0)continue;
                cntadjtmp++;
            }
            if(cntadjtmp>2)return 0;
            if(cntadjtmp<=1)continue;
            for(int id=0;id<4;id++)
            {
                int ni=i+dx[id],nj=j+dy[id];
                if(ni<0 or ni>=n or nj<0 or nj>=n)continue;
                if(tmp[ni][nj]==0)continue;
                if(r1==-1){r1=ni;c1=nj;}
                else
                {
                    if(r1==ni or c1==nj)return 0;
                }
            }
        }
    }
    return 1;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    int empsz=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            a[i][j]=F[i][j];
            if(a[i][j]==0){empsz++;tmp[i][j]=1;}
        }
    }
    if(check())return empsz;
    return -1;
}

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