Submission #338791

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338791	2020-12-23T22:46:50 Z	couplefire	Robots (APIO13_robots)	C++17	Compilation error	0 ms	0 KB

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

robots.cpp: In function 'void prep(int, int, int)':
robots.cpp:56:5: error: reference to 'hash' is ambiguous
   56 |  dp[hash[id][id+1]][sy][sx]=0;
      |     ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:67:10: error: reference to 'hash' is ambiguous
   67 |    if(dp[hash[id][id+1]][to.fr][to.sc]!=-1) continue;
      |          ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:69:7: error: reference to 'hash' is ambiguous
   69 |    dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
      |       ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:69:40: error: reference to 'hash' is ambiguous
   69 |    dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
      |                                        ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:75:26: error: reference to 'hash' is ambiguous
   75 |  REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
      |                          ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:75:56: error: reference to 'hash' is ambiguous
   75 |  REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
      |                                                        ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp: In function 'int main()':
robots.cpp:83:26: error: reference to 'hash' is ambiguous
   83 |  REP(i,9) REPN(j,10,i+1) hash[i][j]=cntt++;
      |                          ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:109:7: error: reference to 'hash' is ambiguous
  109 |    dp[hash[i][j]][y][x]=INF;
      |       ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:112:8: error: reference to 'hash' is ambiguous
  112 |     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]);
      |        ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:112:33: error: reference to 'hash' is ambiguous
  112 |     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]);
      |                                 ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:112:54: error: reference to 'hash' is ambiguous
  112 |     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]);
      |                                                      ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:112:77: error: reference to 'hash' is ambiguous
  112 |     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]);
      |                                                                             ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:114:10: error: reference to 'hash' is ambiguous
  114 |    if(dp[hash[i][j]][y][x]!=INF){
      |          ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:115:16: error: reference to 'hash' is ambiguous
  115 |     used.pb(dp[hash[i][j]][y][x]);
      |                ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:116:18: error: reference to 'hash' is ambiguous
  116 |     posByCost[dp[hash[i][j]][y][x]].pb(mp(y,x));
      |                  ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:117:25: error: reference to 'hash' is ambiguous
  117 |     mini=min(mini,mp(dp[hash[i][j]][y][x],mp(y,x)));
      |                         ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:128:13: error: reference to 'hash' is ambiguous
  128 |    int c=dp[hash[i][j]][p.fr][p.sc];
      |             ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:132:12: error: reference to 'hash' is ambiguous
  132 |      if(dp[hash[i][j]][p2.fr][p2.sc]<c+1) continue;
      |            ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from robots.cpp:1:
/usr/include/c++/9/bits/functional_hash.h:58:12: note: candidates are: 'template<class _Tp> struct std::hash'
   58 |     struct hash;
      |            ^~~~
robots.cpp:52:5: note:                 'int hash [10][10]'
   52 | int hash[10][10];
      |     ^~~~
robots.cpp:139:25: error: reference to 'hash' is ambiguous
  139 |     if(nxt.fr==-2 || dp[hash[i][j]][nxt.fr][nxt.sc]<=c+1) continue;
      |                         ^~~~
In file included from /usr/include/c++/9/string_view:43,
                 from /usr/include/c++/9/bits/basic_string.h:48,
                 from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/stdexcept:39,
                 from /usr/include/c++/9/array:39,
                 from /usr/include/c++/9/tuple:39,
                 from /usr/include/c++/9/functional:54,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h