oj.uz

Submission #581529

# Submission time Handle Problem Language Result Execution time Memory
581529 2022-06-22T17:33:40 Z ansol4328 Robots (APIO13_robots) C++14
100 / 100
 492 ms 110832 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef pair<short,short> P;
 
struct A{
    short y, x, dir;
};
 
int n, w, h;
string xy[505];
P nxt[505][505][4];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
vector<vector<int>> D[10][10];
vector<P> nQ[130000*8+5];
bool chk[505][505];
const int INF=1e9;

void fastio(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
}
 
void get_nxt()
{
    queue<A> Q;
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(xy[i][j]=='x') continue;
            for(int k=0 ; k<4 ; k++){
                nxt[i][j][k]=P(-1,-1);
                int ny=i+dy[k], nx=j+dx[k];
                if(ny<0 || ny>=h || nx<0 || nx>=w || xy[ny][nx]=='x'){
                    nxt[i][j][k]=P(i,j);
                    Q.push({(short)i,(short)j,(short)k});
                }
            }
        }
    }
    while(!Q.empty()){
        A v=Q.front(); Q.pop();
        P pr=nxt[v.y][v.x][v.dir];
        if(xy[v.y][v.x]=='A') v.dir=(v.dir+1)%4;
        else if(xy[v.y][v.x]=='C') v.dir=(v.dir+3)%4;
        v.dir=(v.dir+2)%4;
        v.y+=dy[v.dir], v.x+=dx[v.dir];
        if(v.y<0 || v.y>=h || v.x<0 || v.x>=w || xy[v.y][v.x]=='x') continue;
        v.dir=(v.dir+2)%4;
        nxt[v.y][v.x][v.dir]=pr; Q.push(v);
    }
}
 
void prop(int s, int e)
{
    memset(chk,false,sizeof(chk));
    int mn=INF, mx=0;
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(D[s][e][i][j]!=-1){
                nQ[D[s][e][i][j]].pb(P(i,j));
                mn=min(mn,D[s][e][i][j]);
                mx=max(mx,D[s][e][i][j]);
            }
        }
    }
    while(mn<=mx){
        vector<P> &cur=nQ[mn];
        if(cur.empty()){
            vector<P>().swap(cur);
            mn++; continue;
        }
        P v=cur.back(); cur.pop_back();
        if(chk[v.fi][v.se]) continue;
        chk[v.fi][v.se]=true;
        for(int i=0 ; i<4 ; i++){
            if(nxt[v.fi][v.se][i]==P(-1,-1)) continue;
            P nv=nxt[v.fi][v.se][i];
            if(!chk[nv.fi][nv.se] && (D[s][e][nv.fi][nv.se]==-1 || D[s][e][nv.fi][nv.se]>D[s][e][v.fi][v.se]+1)){
                D[s][e][nv.fi][nv.se]=D[s][e][v.fi][v.se]+1;
                nQ[D[s][e][nv.fi][nv.se]].pb(nv);
                mx=max(mx,D[s][e][nv.fi][nv.se]);
            }
        }
    }
}
 
int main()
{
    fastio();
    cin >> n >> w >> h;
    for(int i=0 ; i<h ; i++) cin >> xy[i];
    get_nxt();
    for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=n ; j++) D[i][j].resize(h,vector<int>(w,-1));
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(xy[i][j]>='1' && xy[i][j]<='9'){
                D[xy[i][j]-'0'][xy[i][j]-'0'][i][j]=0;
                prop(xy[i][j]-'0',xy[i][j]-'0');
            }
        }
    }
    for(int x=1 ; x<n ; x++){
        for(int i=1, j=1+x ; i+x<=n ; i++, j++){
            for(int c=i ; c<j ; c++){
                for(int y=0 ; y<h ; y++){
                    for(int x=0 ; x<w ; x++){
                        if(D[i][c][y][x]==-1 || D[c+1][j][y][x]==-1) continue;
                        if(D[i][j][y][x]==-1 || D[i][j][y][x]>D[i][c][y][x]+D[c+1][j][y][x]) D[i][j][y][x]=D[i][c][y][x]+D[c+1][j][y][x];
                    }
                }
            }
            prop(i,j);
        }
    }
    int ans=-1;
    for(int i=0 ; i<h ; i++) for(int j=0 ; j<w ; j++) if(D[1][n][i][j]!=-1 && (ans==-1 || ans>D[1][n][i][j])) ans=D[1][n][i][j];
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24916 KB Output is correct
2 Correct 14 ms 24980 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 13 ms 25068 KB Output is correct
5 Correct 16 ms 25064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24916 KB Output is correct
2 Correct 14 ms 24980 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 13 ms 25068 KB Output is correct
5 Correct 16 ms 25064 KB Output is correct
6 Correct 14 ms 24984 KB Output is correct
7 Correct 16 ms 24976 KB Output is correct
8 Correct 16 ms 25028 KB Output is correct
9 Correct 15 ms 24908 KB Output is correct
10 Correct 14 ms 25044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24916 KB Output is correct
2 Correct 14 ms 24980 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 13 ms 25068 KB Output is correct
5 Correct 16 ms 25064 KB Output is correct
6 Correct 14 ms 24984 KB Output is correct
7 Correct 16 ms 24976 KB Output is correct
8 Correct 16 ms 25028 KB Output is correct
9 Correct 15 ms 24908 KB Output is correct
10 Correct 14 ms 25044 KB Output is correct
11 Correct 86 ms 56652 KB Output is correct
12 Correct 18 ms 27860 KB Output is correct
13 Correct 31 ms 45256 KB Output is correct
14 Correct 174 ms 56800 KB Output is correct
15 Correct 69 ms 56480 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24916 KB Output is correct
2 Correct 14 ms 24980 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 13 ms 25068 KB Output is correct
5 Correct 16 ms 25064 KB Output is correct
6 Correct 14 ms 24984 KB Output is correct
7 Correct 16 ms 24976 KB Output is correct
8 Correct 16 ms 25028 KB Output is correct
9 Correct 15 ms 24908 KB Output is correct
10 Correct 14 ms 25044 KB Output is correct
11 Correct 86 ms 56652 KB Output is correct
12 Correct 18 ms 27860 KB Output is correct
13 Correct 31 ms 45256 KB Output is correct
14 Correct 174 ms 56800 KB Output is correct
15 Correct 69 ms 56480 KB Output is correct
16 Correct 99 ms 110124 KB Output is correct
17 Correct 492 ms 110832 KB Output is correct
18 Correct 154 ms 110240 KB Output is correct
19 Correct 92 ms 110240 KB Output is correct
20 Correct 383 ms 110568 KB Output is correct