oj.uz

Submission #726074

# Submission time Handle Problem Language Result Execution time Memory
726074 2023-04-18T12:24:01 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 555 ms 72296 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
#define visit lonmemayto
const int inf=1e9;
int v1[]={-1,0,1,0};
int v2[]={0,1,0,-1};
char a[509][509];
pii nxt[509][509][4];
int dp[9][9][509][509];
vector<pii>g[509][509];
int vis[9][9];
pii pos[9];
int n,r,c;
pii cal(int i,int j,int hr){
    if (nxt[i][j][hr]!=pii(0,0))return nxt[i][j][hr];
    //cout<<i<<" "<<j<<" "<<hr<<'\n';
    int lt=hr;
    if (a[i][j]=='A')hr=(hr-1+4)%4;
    if (a[i][j]=='C')hr=(hr+1)%4;
    nxt[i][j][lt]={-1,-1};
    //cout<<i<<" "<<j<<" "<<hr<<" "<<lt<<'\n';
    int newi=i+v1[hr],newj=j+v2[hr];
    if (newi==0||newj==0||newi>r||newj>c||a[newi][newj]=='x')return nxt[i][j][lt]={i,j};
    return nxt[i][j][lt]=cal(newi,newj,hr);
}
int visit[509][509];
struct ver{
int i,j,dis;
bool operator < (const ver &p)const {
return dis>p.dis;
}
};
void cal(int l1,int r1){
if (vis[l1][r1])return;
vis[l1][r1]=1;
if (l1==r1){
    for1(i,1,r){
    for1(j,1,c){
    dp[l1][l1][i][j]=inf;
    }
    }
    dp[l1][l1][pos[l1].fi][pos[l1].se]=0;
    memset(visit,0,sizeof(visit));
    visit[pos[l1].fi][pos[l1].se]=1;
    queue<pii>t;
    t.push(pos[l1]);
    while (!t.empty()){
        auto u=t.front();
        t.pop();
        for (auto v:g[u.fi][u.se]){
            if (visit[v.fi][v.se])continue;
            visit[v.fi][v.se]=1;
            dp[l1][l1][v.fi][v.se]=dp[l1][l1][u.fi][u.se]+1;
            t.push(v);
        }
    }
    return;
}
for1(i,1,r){
for1(j,1,c){
dp[l1][r1][i][j]=inf;
}
}
for1(id,l1,r1-1){
cal(l1,id);
cal(id+1,r1);
for1(i,1,r){
for1(j,1,c){
dp[l1][r1][i][j]=min({dp[l1][r1][i][j],inf,dp[l1][id][i][j]+dp[id+1][r1][i][j]});
}
}
}
memset(visit,0,sizeof( visit));
vector<ver>vcl;
for1(i,1,r){
for1(j,1,c){
if (dp[l1][r1][i][j]>=inf)continue;
vcl.pb({i,j,dp[l1][r1][i][j]});
}
}
sort(all(vcl));
deque<ver>t;
while (sz(t)||sz(vcl)){
    if (t.empty()){
        t.pb(vcl.back());
        vcl.pop_back();
    }
    else {
        if (sz(vcl)){
            if (vcl.back().dis<t.front().dis){
            t.push_front(vcl.back());
            vcl.pop_back();
            }
        }
    }
    auto u=t.front();
    t.pop_front();
    //cout<<u.i<<" "<<u.j<<" "<<u.dis<<'\n';
    if (visit[u.i][u.j])continue;
    dp[l1][r1][u.i][u.j]=u.dis;
    visit[u.i][u.j]=1;
    for (auto v:g[u.i][u.j]){
        if (visit[v.fi][v.se])continue;
        ver ttt={v.fi,v.se,u.dis+1};
        //if (u.i==1&&u.j==7)cout<<u.dis+1<<'\n';
        t.pb(ttt);
    }
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n>>c>>r;
    for1(i,1,r){
    for1(j,1,c){
    cin>>a[i][j];
    if (a[i][j]!='.'&&a[i][j]!='x'&&a[i][j]!='A'&&a[i][j]!='C'){
        pos[a[i][j]-'1']={i,j};
    }
    }
    }
    //cal(5,5,1);
    for1(i,1,r){
    for1(j,1,c){
    if (a[i][j]!='x'){
        for1(k,0,3){
        cal(i,j,k);
        if (nxt[i][j][k]!=pii(-1,-1)&&nxt[i][j][k]!=pii(i,j)){
            g[i][j].pb(nxt[i][j][k]);
        }
        }
    }
    }
    }
    //cal(5,5,1);
    cal(0,n-1);
    int ans=inf;
    for1(i,1,r){
    for1(j,1,c){
    ans=min(ans,dp[0][n-1][i][j]);
    }
    }
    //cal(2,3);
    //cout<<dp[2][3][1][1];
    if (ans>=inf)cout<<-1;
    else cout<<ans;
    //cout<<dp[2][3][1][1];
    //cout<<pos[2].fi<<" "<<pos[2].se;
    //cout<<nxt[pos[2].fi][pos[2].se][1].fi<<" "<<nxt[pos[2].fi][pos[2].se][1].se;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7440 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7440 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7440 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7428 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7440 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7440 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7428 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7492 KB Output is correct
11 Correct 116 ms 39900 KB Output is correct
12 Correct 15 ms 12788 KB Output is correct
13 Correct 37 ms 29964 KB Output is correct
14 Correct 260 ms 40364 KB Output is correct
15 Correct 74 ms 39280 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7440 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7440 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7428 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7492 KB Output is correct
11 Correct 116 ms 39900 KB Output is correct
12 Correct 15 ms 12788 KB Output is correct
13 Correct 37 ms 29964 KB Output is correct
14 Correct 260 ms 40364 KB Output is correct
15 Correct 74 ms 39280 KB Output is correct
16 Correct 142 ms 72296 KB Output is correct
17 Correct 555 ms 66028 KB Output is correct
18 Correct 139 ms 64516 KB Output is correct
19 Correct 107 ms 64780 KB Output is correct
20 Correct 380 ms 65700 KB Output is correct