oj.uz

Submission #581475

# Submission time Handle Problem Language Result Execution time Memory
581475 2022-06-22T16:48:25 Z ansol4328 Robots (APIO13_robots) C++14
60 / 100
 1500 ms 146400 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)
{
    map<int,queue<P>> Q;
    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]].push(P(i,j));
                mn=min(mn,D[s][e][i][j]);
                mx=max(mx,D[s][e][i][j]);
            }
        }
    }
    while(mn<=mx){
        queue<P> &cur=Q[mn];
        if(cur.empty()){
            mn++; continue;
        }
        P v=cur.front(); cur.pop();
        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]].push(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 48 ms 100056 KB Output is correct
2 Correct 42 ms 100040 KB Output is correct
3 Correct 43 ms 100044 KB Output is correct
4 Correct 44 ms 100092 KB Output is correct
5 Correct 42 ms 100188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100056 KB Output is correct
2 Correct 42 ms 100040 KB Output is correct
3 Correct 43 ms 100044 KB Output is correct
4 Correct 44 ms 100092 KB Output is correct
5 Correct 42 ms 100188 KB Output is correct
6 Correct 42 ms 100048 KB Output is correct
7 Correct 42 ms 100024 KB Output is correct
8 Correct 48 ms 100272 KB Output is correct
9 Correct 46 ms 100148 KB Output is correct
10 Correct 43 ms 100164 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100056 KB Output is correct
2 Correct 42 ms 100040 KB Output is correct
3 Correct 43 ms 100044 KB Output is correct
4 Correct 44 ms 100092 KB Output is correct
5 Correct 42 ms 100188 KB Output is correct
6 Correct 42 ms 100048 KB Output is correct
7 Correct 42 ms 100024 KB Output is correct
8 Correct 48 ms 100272 KB Output is correct
9 Correct 46 ms 100148 KB Output is correct
10 Correct 43 ms 100164 KB Output is correct
11 Correct 402 ms 116404 KB Output is correct
12 Correct 55 ms 113772 KB Output is correct
13 Correct 64 ms 105364 KB Output is correct
14 Correct 700 ms 119308 KB Output is correct
15 Correct 209 ms 115292 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100056 KB Output is correct
2 Correct 42 ms 100040 KB Output is correct
3 Correct 43 ms 100044 KB Output is correct
4 Correct 44 ms 100092 KB Output is correct
5 Correct 42 ms 100188 KB Output is correct
6 Correct 42 ms 100048 KB Output is correct
7 Correct 42 ms 100024 KB Output is correct
8 Correct 48 ms 100272 KB Output is correct
9 Correct 46 ms 100148 KB Output is correct
10 Correct 43 ms 100164 KB Output is correct
11 Correct 402 ms 116404 KB Output is correct
12 Correct 55 ms 113772 KB Output is correct
13 Correct 64 ms 105364 KB Output is correct
14 Correct 700 ms 119308 KB Output is correct
15 Correct 209 ms 115292 KB Output is correct
16 Correct 115 ms 108536 KB Output is correct
17 Execution timed out 1600 ms 146400 KB Time limit exceeded
18 Halted 0 ms 0 KB -