Submission #42552

#	Time	Username	Problem	Language	Result	Execution time	Memory
42552		funcsr	Robots (APIO13_robots)	C++14	Compilation error	0 ms	0 KiB

robots

#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 (stderr)

robots.cpp: In function 'void prep(int, int, int)':
robots.cpp:56:12: error: reference to 'hash' is ambiguous
         dp[hash[id][id+1]][sy][sx]=0;
            ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:67:31: error: reference to 'hash' is ambiguous
                         if(dp[hash[id][id+1]][to.fr][to.sc]!=-1) continue;
                               ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:69:28: error: reference to 'hash' is ambiguous
                         dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
                            ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:69:61: error: reference to 'hash' is ambiguous
                         dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
                                                             ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:75:33: error: reference to 'hash' is ambiguous
         REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
                                 ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:75:63: error: reference to 'hash' is ambiguous
         REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
                                                               ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp: In function 'int main()':
robots.cpp:83:33: error: reference to 'hash' is ambiguous
         REP(i,9) REPN(j,10,i+1) hash[i][j]=cntt++;
                                 ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:109:28: error: reference to 'hash' is ambiguous
                         dp[hash[i][j]][y][x]=INF;
                            ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:112:36: error: reference to 'hash' is ambiguous
                                 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]);
                                    ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:112:61: error: reference to 'hash' is ambiguous
                                 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]);
                                                             ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:112:82: error: reference to 'hash' is ambiguous
                                 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]);
                                                                                  ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:112:105: error: reference to 'hash' is ambiguous
                                 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]);
                                                                                                         ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:114:31: error: reference to 'hash' is ambiguous
                         if(dp[hash[i][j]][y][x]!=INF){
                               ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:115:44: error: reference to 'hash' is ambiguous
                                 used.pb(dp[hash[i][j]][y][x]);
                                            ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:116:46: error: reference to 'hash' is ambiguous
                                 posByCost[dp[hash[i][j]][y][x]].pb(mp(y,x));
                                              ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:117:53: error: reference to 'hash' is ambiguous
                                 mini=min(mini,mp(dp[hash[i][j]][y][x],mp(y,x)));
                                                     ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:128:34: error: reference to 'hash' is ambiguous
                         int c=dp[hash[i][j]][p.fr][p.sc];
                                  ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:132:47: error: reference to 'hash' is ambiguous
                                         if(dp[hash[i][j]][p2.fr][p2.sc]<c+1) continue;
                                               ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:139:53: error: reference to 'hash' is ambiguous
                                 if(nxt.fr==-2 || dp[hash[i][j]][nxt.fr][nxt.sc]<=c+1) continue;
                                                     ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:140:36: error: reference to 'hash' is ambiguous
                                 dp[hash[i][j]][nxt.fr][nxt.sc]=c+1;
                                    ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
robots.cpp:153:42: error: reference to 'hash' is ambiguous
         REP(i,h) REP(j,w) res=min(res,dp[hash[0][n]][i][j]);
                                          ^
robots.cpp:52:5: note: candidates are: int hash [10][10]
 int hash[10][10];
     ^
In file included from /usr/include/c++/5/bits/basic_string.h:5471:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/random:40,
                 from /usr/include/c++/5/bits/stl_algo.h:66,
                 from /usr/include/c++/5/algorithm:62,
                 from robots.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: note:                 template<class _Tp> struct std::hash
     struct hash;
            ^
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]);
                                    ^