Submission #160402

#	Time	Username	Problem	Language	Result	Execution time	Memory
160402		arnold518	Robots (APIO13_robots)	C++14	100 / 100	926 ms	63744 KiB

robots

#pragma GCC optimize ("Ofast")
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 500;
const int INF = 987654321;
const int MAXVAL = 1e6;
 
const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};
const int dA[]={2, 3, 1, 0};
const int dC[]={3, 2, 0, 1};
 
int N, W, H;
char A[MAXN+10][MAXN+10];
pii dest[MAXN+10][MAXN+10][4];
int dp[10][10][MAXN+10][MAXN+10];
 
void dfs(int y, int x, int dir)
{
    if(dest[y][x][dir]!=pii(-1, -1)) return;
    int ndir;
    if(A[y][x]=='A') ndir=dA[dir];
    else if(A[y][x]=='C') ndir=dC[dir];
    else ndir=dir;
 
    int ny=y+dy[ndir], nx=x+dx[ndir];
    if(A[ny][nx]=='x')
    {
        dest[y][x][dir]={y, x};
        return;
    }
    dfs(ny, nx, ndir);
    dest[y][x][dir]=dest[ny][nx][ndir];
}
 
struct Queue
{
    int y, x, w;
    bool operator < (const Queue &p) const { return w>p.w; }
};
 
struct dequeue
{
    Queue arr[MAXVAL];
    int l, r;
    void init() { l=r=MAXVAL/2; }
    Queue front() { return arr[l]; }
    void push_back(Queue x) { arr[r++]=x; }
    void push_front(Queue x) { arr[--l]=x; }
    void pop_front () { l++; }
    bool empty() { return l==r; }
};
dequeue Q;
 
int main()
{
    int i, j, k, p, q;
 
    scanf("%d%d%d", &N, &W, &H);
    for(i=1; i<=H; i++) scanf("%s", A[i]+1);
    for(i=0; i<=H+1; i++) A[i][0]=A[i][W+1]='x';
    for(j=0; j<=W+1; j++) A[0][j]=A[H+1][j]='x';
 
    for(i=1; i<=H; i++) for(j=1; j<=W; j++) for(k=0; k<4; k++) dest[i][j][k]={-1, -1};
    for(i=1; i<=H; i++) for(j=1; j<=W; j++) for(k=0; k<4; k++)
    {
        if(dest[i][j][k]!=pii(-1, -1)) continue;
        dfs(i, j, k);
    }
    //for(i=1; i<=H; i++) { for(j=1; j<=W; j++) printf("(%d %d / %d %d / %d %d / %d %d) ", dest[i][j][0].first, dest[i][j][0].second, dest[i][j][1].first, dest[i][j][1].second, dest[i][j][2].first, dest[i][j][2].second, dest[i][j][3].first, dest[i][j][3].second); printf("\n"); }
 
    for(q=1; q<=N; q++) for(p=q; p>=1; p--)
    {
        vector<Queue> PQ;
        for(i=1; i<=H; i++) for(j=1; j<=W; j++) dp[p][q][i][j]=INF;
        if(p==q)
        {
            for(i=1; i<=H; i++) for(j=1; j<=W; j++)
            {
                int now;
                if(A[i][j]=='0'+p) now=0;
                else now=INF;
                PQ.push_back({i, j, now});
            }
        }
        else
        {
            for(i=1; i<=H; i++) for(j=1; j<=W; j++)
            {
                int now=INF;
                for(k=p; k<q; k++)
                {
                    now=min(now, dp[p][k][i][j]+dp[k+1][q][i][j]);
                }
                PQ.push_back({i, j, now});
            }
        }
        sort(PQ.begin(), PQ.end());
        Q.init();
        Q.push_back(PQ.back()); PQ.pop_back();
 
        while(!Q.empty())
        {
            while(!PQ.empty() && PQ.back().w==Q.front().w) Q.push_front(PQ.back()), PQ.pop_back();
            Queue T=Q.front(); Q.pop_front();
            //printf("%d %d %d\n", T.y, T.x, T.w);
            if(dp[p][q][T.y][T.x]<=T.w) continue;
            dp[p][q][T.y][T.x]=T.w;
            for(k=0; k<4; k++) if(dp[p][q][dest[T.y][T.x][k].first][dest[T.y][T.x][k].second]>T.w+1) Q.push_back({dest[T.y][T.x][k].first, dest[T.y][T.x][k].second, T.w+1});//, printf("?%d %d %d\n", dest[T.y][T.x][k].first, dest[T.y][T.x][k].second, T.w+1);
        }
        //printf("=======%d %d========\n", p, q);
        //for(i=1; i<=H; i++) { for(j=1; j<=W; j++) printf("%d ", dp[p][q][i][j]); printf("\n"); }
    }
    int ans=INF;
    for(i=1; i<=H; i++) for(j=1; j<=W; j++) ans=min(ans, dp[1][N][i][j]);
    if(ans==INF) printf("-1");
    else printf("%d", ans);
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &W, &H);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:66:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=H; i++) scanf("%s", A[i]+1);
                         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40