oj.uz

Submission #581520

# Submission time Handle Problem Language Result Execution time Memory
581520 2022-06-22T17:24:48 Z ansol4328 Robots (APIO13_robots) C++14
100 / 100
 521 ms 134576 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+5,vector<int>(w+5,-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 23 ms 47216 KB Output is correct
4 Correct 24 ms 47232 KB Output is correct
5 Correct 22 ms 47276 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 23 ms 47216 KB Output is correct
4 Correct 24 ms 47232 KB Output is correct
5 Correct 22 ms 47276 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 24 ms 47184 KB Output is correct
8 Correct 28 ms 47228 KB Output is correct
9 Correct 25 ms 47320 KB Output is correct
10 Correct 27 ms 47376 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 23 ms 47216 KB Output is correct
4 Correct 24 ms 47232 KB Output is correct
5 Correct 22 ms 47276 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 24 ms 47184 KB Output is correct
8 Correct 28 ms 47228 KB Output is correct
9 Correct 25 ms 47320 KB Output is correct
10 Correct 27 ms 47376 KB Output is correct
11 Correct 100 ms 79736 KB Output is correct
12 Correct 29 ms 50072 KB Output is correct
13 Correct 45 ms 68132 KB Output is correct
14 Correct 208 ms 79824 KB Output is correct
15 Correct 82 ms 79660 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 23 ms 47216 KB Output is correct
4 Correct 24 ms 47232 KB Output is correct
5 Correct 22 ms 47276 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 24 ms 47184 KB Output is correct
8 Correct 28 ms 47228 KB Output is correct
9 Correct 25 ms 47320 KB Output is correct
10 Correct 27 ms 47376 KB Output is correct
11 Correct 100 ms 79736 KB Output is correct
12 Correct 29 ms 50072 KB Output is correct
13 Correct 45 ms 68132 KB Output is correct
14 Correct 208 ms 79824 KB Output is correct
15 Correct 82 ms 79660 KB Output is correct
16 Correct 116 ms 133864 KB Output is correct
17 Correct 521 ms 134576 KB Output is correct
18 Correct 188 ms 133892 KB Output is correct
19 Correct 120 ms 133876 KB Output is correct
20 Correct 350 ms 134264 KB Output is correct