oj.uz

Submission #581526

# Submission time Handle Problem Language Result Execution time Memory
581526 2022-06-22T17:32:03 Z ansol4328 Robots (APIO13_robots) C++14
100 / 100
 476 ms 110944 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[130000*8+5];
bool chk[505][505];
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)
{
    memset(chk,false,sizeof(chk));
    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 12 ms 24916 KB Output is correct
2 Correct 14 ms 24916 KB Output is correct
3 Correct 13 ms 24896 KB Output is correct
4 Correct 13 ms 25060 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Correct 14 ms 24916 KB Output is correct
3 Correct 13 ms 24896 KB Output is correct
4 Correct 13 ms 25060 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 25024 KB Output is correct
7 Correct 13 ms 24892 KB Output is correct
8 Correct 13 ms 24916 KB Output is correct
9 Correct 13 ms 24996 KB Output is correct
10 Correct 13 ms 25044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Correct 14 ms 24916 KB Output is correct
3 Correct 13 ms 24896 KB Output is correct
4 Correct 13 ms 25060 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 25024 KB Output is correct
7 Correct 13 ms 24892 KB Output is correct
8 Correct 13 ms 24916 KB Output is correct
9 Correct 13 ms 24996 KB Output is correct
10 Correct 13 ms 25044 KB Output is correct
11 Correct 84 ms 56616 KB Output is correct
12 Correct 18 ms 27732 KB Output is correct
13 Correct 31 ms 45280 KB Output is correct
14 Correct 176 ms 56796 KB Output is correct
15 Correct 60 ms 56404 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Correct 14 ms 24916 KB Output is correct
3 Correct 13 ms 24896 KB Output is correct
4 Correct 13 ms 25060 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 25024 KB Output is correct
7 Correct 13 ms 24892 KB Output is correct
8 Correct 13 ms 24916 KB Output is correct
9 Correct 13 ms 24996 KB Output is correct
10 Correct 13 ms 25044 KB Output is correct
11 Correct 84 ms 56616 KB Output is correct
12 Correct 18 ms 27732 KB Output is correct
13 Correct 31 ms 45280 KB Output is correct
14 Correct 176 ms 56796 KB Output is correct
15 Correct 60 ms 56404 KB Output is correct
16 Correct 96 ms 110008 KB Output is correct
17 Correct 476 ms 110944 KB Output is correct
18 Correct 130 ms 110080 KB Output is correct
19 Correct 92 ms 110076 KB Output is correct
20 Correct 301 ms 110480 KB Output is correct