Submission #897147

#	Time	Username	Problem	Language	Result	Execution time	Memory
897147		Aiperiii	Golf (JOI17_golf)	C++14	0 / 100	79 ms	70740 KiB

golf

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1e3+5;
int dis[N][N][2],vld[N][N],vis[N][N][2],frnd[N][N][4];
signed main(){
    int s,t,u,v;
    cin>>s>>t>>u>>v;
    int n;
    cin>>n;
    for(int i=1;i<N;i++){
        for(int j=1;j<N;j++){
            frnd[i][j][0]=1;
            frnd[i][j][1]=1;
            frnd[i][j][2]=1;
            frnd[i][j][3]=1;
        }
    }
    for(int i=0;i<n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        for(int x=a;x<=b;x++){
            for(int y=c;y<=d;y++){
                vld[x][y]=2;
            }
        }
        for(int x=a;x<=b;x++){
            vld[x][c]=1;vld[x][d]=1;
        }
        for(int x=a+1;x<b;x++){
            frnd[x][c][2]=0;
            frnd[x][d][3]=0;
        }
        for(int y=c;y<=d;y++){
            vld[a][y]=1;vld[b][y]=1;
        }
        for(int y=c+1;y<d;y++){
            frnd[a][y][0]=0;
            frnd[b][y][1]=0;
        }
    }
    queue <pair <int,int> > q;
    q.push({s,t});
    q.push({s,t});
    vis[s][t][0]=1;
    vis[s][t][1]=1;
    dis[s][t][1]=1;
    dis[s][t][0]=1;
    while(!q.empty()){
        int x=q.front().ff;
        int y=q.front().ss;
        q.pop();
        if(x+1<=1000 && vld[x+1][y]<=1 && !vis[x+1][y][0] && frnd[x][y][0]){
            if(dis[x][y][0]){
                vis[x+1][y][0]=1;
                dis[x+1][y][0]=dis[x][y][0];
                q.push({x+1,y});
            }
            else if(dis[x][y][1]){
                vis[x+1][y][0]=1;
                dis[x+1][y][0]=dis[x][y][1]+1;
                q.push({x+1,y});
            }
        }
        if(x-1>=1 && vld[x-1][y]<=1 && !vis[x-1][y][0] && frnd[x][y][1]){
            if(dis[x][y][0]){
                vis[x-1][y][0]=1;
                dis[x-1][y][0]=dis[x][y][0];
                q.push({x-1,y});
            }
            else if(dis[x][y][1]){
                vis[x-1][y][0]=1;
                dis[x-1][y][0]=dis[x][y][1]+1;
                q.push({x-1,y});
            }
        }
        if(y+1<=1000 && vld[x][y+1]<=1 && !vis[x][y+1][1] && frnd[x][y][2]){
            if(dis[x][y][1]){
                vis[x][y+1][1]=1;
                dis[x][y+1][1]=dis[x][y][1];
                q.push({x,y+1});
            }
            else if(dis[x][y][0]){
                vis[x][y+1][1]=1;
                dis[x][y+1][1]=dis[x][y][0]+1;
                q.push({x,y+1});
            }
        }
        if(y-1>=1 && vld[x][y-1]<=1 && !vis[x][y-1][1] && frnd[x][y][3]){
            if(dis[x][y][1]){
                vis[x][y-1][1]=1;
                dis[x][y-1][1]=dis[x][y][1];
                q.push({x,y-1});
            }
            else if(dis[x][y][0]){
                vis[x][y-1][1]=1;
                dis[x][y-1][1]=dis[x][y][0]+1;
                q.push({x,y-1});
            }
        }
    }
    cout<<min(dis[u][v][0],dis[u][v][1])<<"\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70