oj.uz

Submission #581522

# Submission time Handle Problem Language Result Execution time Memory
581522 2022-06-22T17:25:52 Z ansol4328 Robots (APIO13_robots) C++14
100 / 100
 514 ms 133068 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[250000*8+5];
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)
{
    vector<vector<bool>> chk(h,vector<bool>(w));
    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 i=1, j=1 ; i<=n ; i++, j++){
            cout << "[ " << i << ' ' << j << " ]\n";
            for(int y=0 ; y<h ; y++){
                for(int x=0 ; x<w ; x++){
                    cout << D[i][j][y][x] << ' ';
                }
                cout << '\n';
            }
        }
    */
    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);
            /*
            cout << "[ " << i << ' ' << j << " ]\n";
            for(int y=0 ; y<h ; y++){
                for(int x=0 ; x<w ; x++){
                    cout << D[i][j][y][x] << ' ';
                }
                cout << '\n';
            }
            */
        }
    }
    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 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 24 ms 47268 KB Output is correct
4 Correct 25 ms 47312 KB Output is correct
5 Correct 24 ms 47264 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 24 ms 47268 KB Output is correct
4 Correct 25 ms 47312 KB Output is correct
5 Correct 24 ms 47264 KB Output is correct
6 Correct 26 ms 47188 KB Output is correct
7 Correct 29 ms 47308 KB Output is correct
8 Correct 30 ms 47320 KB Output is correct
9 Correct 24 ms 47316 KB Output is correct
10 Correct 23 ms 47324 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 24 ms 47268 KB Output is correct
4 Correct 25 ms 47312 KB Output is correct
5 Correct 24 ms 47264 KB Output is correct
6 Correct 26 ms 47188 KB Output is correct
7 Correct 29 ms 47308 KB Output is correct
8 Correct 30 ms 47320 KB Output is correct
9 Correct 24 ms 47316 KB Output is correct
10 Correct 23 ms 47324 KB Output is correct
11 Correct 102 ms 78908 KB Output is correct
12 Correct 29 ms 50004 KB Output is correct
13 Correct 47 ms 67628 KB Output is correct
14 Correct 212 ms 78980 KB Output is correct
15 Correct 86 ms 78808 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 24 ms 47268 KB Output is correct
4 Correct 25 ms 47312 KB Output is correct
5 Correct 24 ms 47264 KB Output is correct
6 Correct 26 ms 47188 KB Output is correct
7 Correct 29 ms 47308 KB Output is correct
8 Correct 30 ms 47320 KB Output is correct
9 Correct 24 ms 47316 KB Output is correct
10 Correct 23 ms 47324 KB Output is correct
11 Correct 102 ms 78908 KB Output is correct
12 Correct 29 ms 50004 KB Output is correct
13 Correct 47 ms 67628 KB Output is correct
14 Correct 212 ms 78980 KB Output is correct
15 Correct 86 ms 78808 KB Output is correct
16 Correct 116 ms 132300 KB Output is correct
17 Correct 514 ms 133068 KB Output is correct
18 Correct 167 ms 132500 KB Output is correct
19 Correct 105 ms 132428 KB Output is correct
20 Correct 351 ms 132780 KB Output is correct