oj.uz

Submission #752810

# Submission time Handle Problem Language Result Execution time Memory
752810 2023-06-04T01:38:08 Z winter0101 Robots (APIO13_robots) C++14
100 / 100
 552 ms 72336 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 4 ms 7636 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 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 4 ms 7636 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7448 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7520 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7636 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7448 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7520 KB Output is correct
11 Correct 84 ms 39804 KB Output is correct
12 Correct 14 ms 12712 KB Output is correct
13 Correct 32 ms 29896 KB Output is correct
14 Correct 197 ms 40340 KB Output is correct
15 Correct 62 ms 39244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7636 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7448 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7520 KB Output is correct
11 Correct 84 ms 39804 KB Output is correct
12 Correct 14 ms 12712 KB Output is correct
13 Correct 32 ms 29896 KB Output is correct
14 Correct 197 ms 40340 KB Output is correct
15 Correct 62 ms 39244 KB Output is correct
16 Correct 127 ms 72336 KB Output is correct
17 Correct 552 ms 66076 KB Output is correct
18 Correct 130 ms 64616 KB Output is correct
19 Correct 103 ms 64732 KB Output is correct
20 Correct 330 ms 65756 KB Output is correct