oj.uz

Submission #897147

# Submission time Handle Problem Language Result Execution time Memory
897147 2024-01-02T15:43:05 Z Aiperiii Golf (JOI17_golf) C++14
0 / 100
 79 ms 70740 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70208 KB Output is correct
2 Correct 64 ms 69456 KB Output is correct
3 Correct 79 ms 70740 KB Output is correct
4 Correct 40 ms 69936 KB Output is correct
5 Incorrect 40 ms 69560 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70208 KB Output is correct
2 Correct 64 ms 69456 KB Output is correct
3 Correct 79 ms 70740 KB Output is correct
4 Correct 40 ms 69936 KB Output is correct
5 Incorrect 40 ms 69560 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 70208 KB Output is correct
2 Correct 64 ms 69456 KB Output is correct
3 Correct 79 ms 70740 KB Output is correct
4 Correct 40 ms 69936 KB Output is correct
5 Incorrect 40 ms 69560 KB Output isn't correct
6 Halted 0 ms 0 KB -