oj.uz

Submission #42553

# Submission time Handle Problem Language Result Execution time Memory
42553 2018-02-28T04:53:49 Z funcsr Robots (APIO13_robots) C++
100 / 100
 651 ms 138656 KB 
#include<algorithm>
#include<vector>
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<queue>
 
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define REP(i,m) for(int i=0;i<(int)m;++i)
#define REPN(i,m,in) for(int i=in;i<(int)m;++i)
#define ALL(t) (t).begin(),(t).end()
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define prl cerr<<"LINE "<<__LINE__<<" is called"<<endl
 
using namespace std;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' '; cerr<<endl ; }
 
typedef pair<int,int> pi;
typedef long long int lint;
const int INF=510000000;
 
char buf[505][505];
int dp[50][505][505];
 
pi g[505][505][4];
 
bool vis[505][505][4];
 
int n,w,h;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
pi rec(int y,int x,int d){
    pi& res=g[y][x][d];
        if(res.fr!=-1) return res;
        if(vis[y][x][d]) return res=mp(-2,-2);
        vis[y][x][d]=1;
 
        if(buf[y][x]=='A') d=(d+1)%4;
        if(buf[y][x]=='C') d=(d+3)%4;
 
        int px=x+dx[d],py=y+dy[d];
        if(px<0 || py<0 || px>=w || py>=h || buf[py][px]=='x'){
                return res=mp(y,x);
        }
        return res=rec(py,px,d);
}
 
pi pos[10];
int hash[10][10];
 
void prep(int sy,int sx,int id){
        queue<pi> q;
        dp[hash[id][id+1]][sy][sx]=0;
        q.push(mp(sy,sx));
 
        while(!q.empty()){
                pi cur=q.front();q.pop();
 
                REP(d,4){
                        pi to=g[cur.fr][cur.sc][d];
 
                        if(to.fr==-2) continue;
 
                        if(dp[hash[id][id+1]][to.fr][to.sc]!=-1) continue;
 
                        dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
 
                        q.push(to);
                }
        }
 
        REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
}
 
vector<pi> posByCost[500*501*10];
vector<int> used;
 
int main(){
        int cntt=0;
        REP(i,9) REPN(j,10,i+1) hash[i][j]=cntt++;
        scanf("%d%d%d",&n,&w,&h);
 
        REP(i,h) scanf("%s",buf[i]);
        REP(i,h) REP(j,w){
                if(buf[i][j]>='1' && buf[i][j]<='9'){
                        pos[buf[i][j]-'1']=mp(i,j);
                }
        }
        memset(g,-1,sizeof(g));
        REP(i,h) REP(j,w) REP(d,4) rec(i,j,d);
 
        memset(dp,-1,sizeof(dp));
        REP(i,n){
                prep(pos[i].fr,pos[i].sc,i);
        }
 
 
        queue<pi> q;
 
        for(int len=2;len<=n;++len) REP(i,n-len+1){
                int j=i+len;
 
                pair<int,pi> mini;mini.fr=INF;
                
                REP(y,h) REP(x,w){
                        dp[hash[i][j]][y][x]=INF;
                        REP(k,len-1){
                                int div=i+k+1;
                                dp[hash[i][j]][y][x]=min(dp[hash[i][j]][y][x],dp[hash[i][div]][y][x]+dp[hash[div][j]][y][x]);
                        }
                        if(dp[hash[i][j]][y][x]!=INF){
                                used.pb(dp[hash[i][j]][y][x]);
                                posByCost[dp[hash[i][j]][y][x]].pb(mp(y,x));
                                mini=min(mini,mp(dp[hash[i][j]][y][x],mp(y,x)));
                        }
                }
                if(mini.fr==INF) continue;
                REP(k,posByCost[mini.fr].size()) q.push(posByCost[mini.fr][k]);
                posByCost[mini.fr].clear();
        
 
                while(!q.empty()){
 
                        pi p=q.front();q.pop();
                        int c=dp[hash[i][j]][p.fr][p.sc];
                        if(!posByCost[c+1].empty()){
                                REP(k,posByCost[c+1].size()){
                                        pi p2=posByCost[c+1][k];
                                        if(dp[hash[i][j]][p2.fr][p2.sc]<c+1) continue;
                                        q.push(p2);
                                }
                                posByCost[c+1].clear();
                        }
                        REP(d,4){
                                pi nxt=g[p.fr][p.sc][d];
                                if(nxt.fr==-2 || dp[hash[i][j]][nxt.fr][nxt.sc]<=c+1) continue;
                                dp[hash[i][j]][nxt.fr][nxt.sc]=c+1;
                                q.push(nxt);
                        }
 
                }
                REP(k,used.size()) posByCost[used[k]].clear();
                used.clear();
        
                
        }
 
        int res=INF;
 
        REP(i,h) REP(j,w) res=min(res,dp[hash[0][n]][i][j]);
 
        if(res==INF) res=-1;
 
        printf("%d\n",res);
 
 
 
        return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:84:33: 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:86:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         REP(i,h) scanf("%s",buf[i]);
                                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 116984 KB Output is correct
2 Correct 93 ms 117216 KB Output is correct
3 Correct 92 ms 117216 KB Output is correct
4 Correct 92 ms 117304 KB Output is correct
5 Correct 93 ms 117372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 116984 KB Output is correct
2 Correct 93 ms 117216 KB Output is correct
3 Correct 92 ms 117216 KB Output is correct
4 Correct 92 ms 117304 KB Output is correct
5 Correct 93 ms 117372 KB Output is correct
6 Correct 108 ms 117372 KB Output is correct
7 Correct 93 ms 117372 KB Output is correct
8 Correct 95 ms 117372 KB Output is correct
9 Correct 93 ms 117372 KB Output is correct
10 Correct 94 ms 117372 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 116984 KB Output is correct
2 Correct 93 ms 117216 KB Output is correct
3 Correct 92 ms 117216 KB Output is correct
4 Correct 92 ms 117304 KB Output is correct
5 Correct 93 ms 117372 KB Output is correct
6 Correct 108 ms 117372 KB Output is correct
7 Correct 93 ms 117372 KB Output is correct
8 Correct 95 ms 117372 KB Output is correct
9 Correct 93 ms 117372 KB Output is correct
10 Correct 94 ms 117372 KB Output is correct
11 Correct 181 ms 121648 KB Output is correct
12 Correct 98 ms 121648 KB Output is correct
13 Correct 117 ms 121648 KB Output is correct
14 Correct 288 ms 124068 KB Output is correct
15 Correct 166 ms 124068 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 116984 KB Output is correct
2 Correct 93 ms 117216 KB Output is correct
3 Correct 92 ms 117216 KB Output is correct
4 Correct 92 ms 117304 KB Output is correct
5 Correct 93 ms 117372 KB Output is correct
6 Correct 108 ms 117372 KB Output is correct
7 Correct 93 ms 117372 KB Output is correct
8 Correct 95 ms 117372 KB Output is correct
9 Correct 93 ms 117372 KB Output is correct
10 Correct 94 ms 117372 KB Output is correct
11 Correct 181 ms 121648 KB Output is correct
12 Correct 98 ms 121648 KB Output is correct
13 Correct 117 ms 121648 KB Output is correct
14 Correct 288 ms 124068 KB Output is correct
15 Correct 166 ms 124068 KB Output is correct
16 Correct 232 ms 124068 KB Output is correct
17 Correct 651 ms 138656 KB Output is correct
18 Correct 283 ms 138656 KB Output is correct
19 Correct 246 ms 138656 KB Output is correct
20 Correct 449 ms 138656 KB Output is correct