oj.uz

Submission #581510

# Submission time Handle Problem Language Result Execution time Memory
581510 2022-06-22T17:16:36 Z ansol4328 Robots (APIO13_robots) C++14
100 / 100
 512 ms 158436 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
struct A{
    int 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};
int D[10][10][505][505];
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({i,j,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();
    memset(D,-1,sizeof(D));
    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 62 ms 147020 KB Output is correct
2 Correct 64 ms 147100 KB Output is correct
3 Correct 63 ms 147020 KB Output is correct
4 Correct 64 ms 147020 KB Output is correct
5 Correct 63 ms 147092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 147020 KB Output is correct
2 Correct 64 ms 147100 KB Output is correct
3 Correct 63 ms 147020 KB Output is correct
4 Correct 64 ms 147020 KB Output is correct
5 Correct 63 ms 147092 KB Output is correct
6 Correct 61 ms 147028 KB Output is correct
7 Correct 66 ms 146984 KB Output is correct
8 Correct 63 ms 147092 KB Output is correct
9 Correct 63 ms 147040 KB Output is correct
10 Correct 63 ms 147144 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 147020 KB Output is correct
2 Correct 64 ms 147100 KB Output is correct
3 Correct 63 ms 147020 KB Output is correct
4 Correct 64 ms 147020 KB Output is correct
5 Correct 63 ms 147092 KB Output is correct
6 Correct 61 ms 147028 KB Output is correct
7 Correct 66 ms 146984 KB Output is correct
8 Correct 63 ms 147092 KB Output is correct
9 Correct 63 ms 147040 KB Output is correct
10 Correct 63 ms 147144 KB Output is correct
11 Correct 132 ms 151312 KB Output is correct
12 Correct 70 ms 151164 KB Output is correct
13 Correct 76 ms 152284 KB Output is correct
14 Correct 222 ms 151372 KB Output is correct
15 Correct 104 ms 151152 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 147020 KB Output is correct
2 Correct 64 ms 147100 KB Output is correct
3 Correct 63 ms 147020 KB Output is correct
4 Correct 64 ms 147020 KB Output is correct
5 Correct 63 ms 147092 KB Output is correct
6 Correct 61 ms 147028 KB Output is correct
7 Correct 66 ms 146984 KB Output is correct
8 Correct 63 ms 147092 KB Output is correct
9 Correct 63 ms 147040 KB Output is correct
10 Correct 63 ms 147144 KB Output is correct
11 Correct 132 ms 151312 KB Output is correct
12 Correct 70 ms 151164 KB Output is correct
13 Correct 76 ms 152284 KB Output is correct
14 Correct 222 ms 151372 KB Output is correct
15 Correct 104 ms 151152 KB Output is correct
16 Correct 125 ms 155320 KB Output is correct
17 Correct 512 ms 156696 KB Output is correct
18 Correct 153 ms 155108 KB Output is correct
19 Correct 122 ms 158436 KB Output is correct
20 Correct 352 ms 156436 KB Output is correct