oj.uz

Submission #581504

# Submission time Handle Problem Language Result Execution time Memory
581504 2022-06-22T17:14:19 Z ansol4328 Robots (APIO13_robots) C++14
60 / 100
 512 ms 163840 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) mn=min(mn,D[s][e][i][j]), mx=max(mx,D[s][e][i][j]);
        }
    }
    for(int i=mn ; i<=min(250000*8+4,mx+w*h) ; i++){
        nQ[i].clear();
        vector<P>().swap(nQ[i]);
    }
    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()){
            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 60 ms 147148 KB Output is correct
2 Correct 61 ms 147028 KB Output is correct
3 Correct 60 ms 146984 KB Output is correct
4 Correct 60 ms 147088 KB Output is correct
5 Correct 58 ms 147148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 147148 KB Output is correct
2 Correct 61 ms 147028 KB Output is correct
3 Correct 60 ms 146984 KB Output is correct
4 Correct 60 ms 147088 KB Output is correct
5 Correct 58 ms 147148 KB Output is correct
6 Correct 62 ms 147044 KB Output is correct
7 Correct 71 ms 146996 KB Output is correct
8 Correct 67 ms 147008 KB Output is correct
9 Correct 60 ms 147020 KB Output is correct
10 Correct 64 ms 147028 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 147148 KB Output is correct
2 Correct 61 ms 147028 KB Output is correct
3 Correct 60 ms 146984 KB Output is correct
4 Correct 60 ms 147088 KB Output is correct
5 Correct 58 ms 147148 KB Output is correct
6 Correct 62 ms 147044 KB Output is correct
7 Correct 71 ms 146996 KB Output is correct
8 Correct 67 ms 147008 KB Output is correct
9 Correct 60 ms 147020 KB Output is correct
10 Correct 64 ms 147028 KB Output is correct
11 Correct 146 ms 152636 KB Output is correct
12 Correct 77 ms 151240 KB Output is correct
13 Correct 100 ms 152332 KB Output is correct
14 Correct 260 ms 155368 KB Output is correct
15 Correct 115 ms 151256 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 147148 KB Output is correct
2 Correct 61 ms 147028 KB Output is correct
3 Correct 60 ms 146984 KB Output is correct
4 Correct 60 ms 147088 KB Output is correct
5 Correct 58 ms 147148 KB Output is correct
6 Correct 62 ms 147044 KB Output is correct
7 Correct 71 ms 146996 KB Output is correct
8 Correct 67 ms 147008 KB Output is correct
9 Correct 60 ms 147020 KB Output is correct
10 Correct 64 ms 147028 KB Output is correct
11 Correct 146 ms 152636 KB Output is correct
12 Correct 77 ms 151240 KB Output is correct
13 Correct 100 ms 152332 KB Output is correct
14 Correct 260 ms 155368 KB Output is correct
15 Correct 115 ms 151256 KB Output is correct
16 Correct 160 ms 155392 KB Output is correct
17 Runtime error 512 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -