Submission #752810

#	Time	Username	Problem	Language	Result	Execution time	Memory
752810		winter0101	Robots (APIO13_robots)	C++14	100 / 100	552 ms	72336 KiB

robots

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40