oj.uz

Submission #581513

# Submission time Handle Problem Language Result Execution time Memory
581513 2022-06-22T17:18:32 Z ansol4328 Robots (APIO13_robots) C++14
100 / 100
 508 ms 154336 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{
    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 59 ms 147056 KB Output is correct
2 Correct 61 ms 147048 KB Output is correct
3 Correct 68 ms 146976 KB Output is correct
4 Correct 62 ms 147020 KB Output is correct
5 Correct 61 ms 147020 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147056 KB Output is correct
2 Correct 61 ms 147048 KB Output is correct
3 Correct 68 ms 146976 KB Output is correct
4 Correct 62 ms 147020 KB Output is correct
5 Correct 61 ms 147020 KB Output is correct
6 Correct 61 ms 147064 KB Output is correct
7 Correct 63 ms 147096 KB Output is correct
8 Correct 66 ms 147196 KB Output is correct
9 Correct 64 ms 147012 KB Output is correct
10 Correct 62 ms 147128 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147056 KB Output is correct
2 Correct 61 ms 147048 KB Output is correct
3 Correct 68 ms 146976 KB Output is correct
4 Correct 62 ms 147020 KB Output is correct
5 Correct 61 ms 147020 KB Output is correct
6 Correct 61 ms 147064 KB Output is correct
7 Correct 63 ms 147096 KB Output is correct
8 Correct 66 ms 147196 KB Output is correct
9 Correct 64 ms 147012 KB Output is correct
10 Correct 62 ms 147128 KB Output is correct
11 Correct 133 ms 150100 KB Output is correct
12 Correct 68 ms 150112 KB Output is correct
13 Correct 91 ms 150684 KB Output is correct
14 Correct 226 ms 150420 KB Output is correct
15 Correct 107 ms 150160 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147056 KB Output is correct
2 Correct 61 ms 147048 KB Output is correct
3 Correct 68 ms 146976 KB Output is correct
4 Correct 62 ms 147020 KB Output is correct
5 Correct 61 ms 147020 KB Output is correct
6 Correct 61 ms 147064 KB Output is correct
7 Correct 63 ms 147096 KB Output is correct
8 Correct 66 ms 147196 KB Output is correct
9 Correct 64 ms 147012 KB Output is correct
10 Correct 62 ms 147128 KB Output is correct
11 Correct 133 ms 150100 KB Output is correct
12 Correct 68 ms 150112 KB Output is correct
13 Correct 91 ms 150684 KB Output is correct
14 Correct 226 ms 150420 KB Output is correct
15 Correct 107 ms 150160 KB Output is correct
16 Correct 131 ms 151444 KB Output is correct
17 Correct 508 ms 154052 KB Output is correct
18 Correct 161 ms 152136 KB Output is correct
19 Correct 128 ms 154336 KB Output is correct
20 Correct 330 ms 153672 KB Output is correct