Submission #1285231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285231		MMihalev	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	1 ms	340 KiB

soccer

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<queue>
#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};
int empsz;
int dist[MAX_N][MAX_N];
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 ok(int phase,int x,int y)
{
    int ni=x+dx[phase],nj=y+dy[phase];
    if(ni<0 or ni>=n or nj<0 or nj>=n)return 0;
    if(tmp[ni][nj]==0)return 0;
    return 1;
}
void reset()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            dist[i][j]=-1;
        }
    }
}
bool checkslow()
{
    vector<pair<int,int>>starts;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(tmp[i][j])starts.push_back({i,j});
        }
    }
    for(auto [sx,sy]:starts)
    {
        queue<pair<int,int>>q;
        q.push({sx,sy});
        reset();
        dist[sx][sy]=0;
        while(q.size())
        {
            int x,y;
            tie(x,y)=q.front();
            q.pop();
            for(int id=0;id<4;id++)
            {
                int ni=x+dx[id],nj=y+dy[id];
                if(ni<0 or ni>=n or nj<0 or nj>=n)continue;
                if(tmp[ni][nj]==0 or dist[ni][nj]!=-1)continue;
                dist[ni][nj]=dist[x][y]+1;
                q.push({x,y});
            }
        }
        for(auto [x,y]:starts)
        {
            if(dist[x][y]!=abs(x-sx)+abs(y-sy))return 0;
        }
    }
    return 1;
}
bool check()
{
    int x=-1,y;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(tmp[i][j] && x==-1)
            {
                x=i;
                y=j;
            }
            used[i][j]=0;
        }
    }
    int phase=0;
    int times=10*n;
    while(times--)
    {
        used[x][y]=1;
        if(phase==4)break;
        while(1)
        {
            used[x][y]=1;
            if(ok((phase+1)%4,x,y))
            {
                x+=dx[(phase+1)%4];
                y+=dy[(phase+1)%4];
                used[x][y]=1;
            }
            else
            {
                phase++;
                break;
            }
            while(ok(phase,x,y))
            {
                x+=dx[phase];
                y+=dy[phase];
                used[x][y]=1;
            }
        }
    }
    int cnt=0;
    //cout<<"\n";
    for(int i=0;i<n;i++)
    {
        int f=-1,s=-2;
        for(int j=0;j<n;j++)
        {
            //cout<<used[i][j];
            if(used[i][j])
            {
                if(f==-1)f=j;
                s=j;
            }
        }
        //cout<<"\n";
        for(int j=f;j<=s;j++)
        {
            if(tmp[i][j]==0)return 0;
            cnt++;
        }
    }
    if(cnt==empsz)return 1;
    return 0;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    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(checkslow())return empsz;
    return -1;
}

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