oj.uz

Submission #581495

# Submission time Handle Problem Language Result Execution time Memory
581495 2022-06-22T17:08:43 Z ansol4328 Robots (APIO13_robots) C++14
60 / 100
 1500 ms 163440 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];
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<P>> Q(n*w*h+5);
    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){
                Q[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=Q[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;
                Q[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 38 ms 100096 KB Output is correct
2 Correct 49 ms 100044 KB Output is correct
3 Correct 41 ms 100044 KB Output is correct
4 Correct 39 ms 100116 KB Output is correct
5 Correct 48 ms 100128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100096 KB Output is correct
2 Correct 49 ms 100044 KB Output is correct
3 Correct 41 ms 100044 KB Output is correct
4 Correct 39 ms 100116 KB Output is correct
5 Correct 48 ms 100128 KB Output is correct
6 Correct 42 ms 100040 KB Output is correct
7 Correct 41 ms 100108 KB Output is correct
8 Correct 39 ms 100088 KB Output is correct
9 Correct 41 ms 100104 KB Output is correct
10 Correct 44 ms 100164 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100096 KB Output is correct
2 Correct 49 ms 100044 KB Output is correct
3 Correct 41 ms 100044 KB Output is correct
4 Correct 39 ms 100116 KB Output is correct
5 Correct 48 ms 100128 KB Output is correct
6 Correct 42 ms 100040 KB Output is correct
7 Correct 41 ms 100108 KB Output is correct
8 Correct 39 ms 100088 KB Output is correct
9 Correct 41 ms 100104 KB Output is correct
10 Correct 44 ms 100164 KB Output is correct
11 Correct 294 ms 122872 KB Output is correct
12 Correct 47 ms 106292 KB Output is correct
13 Correct 141 ms 120172 KB Output is correct
14 Correct 401 ms 123384 KB Output is correct
15 Correct 262 ms 123020 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100096 KB Output is correct
2 Correct 49 ms 100044 KB Output is correct
3 Correct 41 ms 100044 KB Output is correct
4 Correct 39 ms 100116 KB Output is correct
5 Correct 48 ms 100128 KB Output is correct
6 Correct 42 ms 100040 KB Output is correct
7 Correct 41 ms 100108 KB Output is correct
8 Correct 39 ms 100088 KB Output is correct
9 Correct 41 ms 100104 KB Output is correct
10 Correct 44 ms 100164 KB Output is correct
11 Correct 294 ms 122872 KB Output is correct
12 Correct 47 ms 106292 KB Output is correct
13 Correct 141 ms 120172 KB Output is correct
14 Correct 401 ms 123384 KB Output is correct
15 Correct 262 ms 123020 KB Output is correct
16 Correct 1197 ms 161488 KB Output is correct
17 Execution timed out 1556 ms 163440 KB Time limit exceeded
18 Halted 0 ms 0 KB -