Submission #1049036

#TimeUsernameProblemLanguageResultExecution timeMemory
1049036adiyerRobots (APIO13_robots)C++17
100 / 100
221 ms138436 KiB
#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 hsh[10][10]; void prep(int sy,int sx,int id){ queue<pi> q; dp[hsh[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[hsh[id][id+1]][to.fr][to.sc]!=-1) continue; dp[hsh[id][id+1]][to.fr][to.sc]=dp[hsh[id][id+1]][cur.fr][cur.sc]+1; q.push(to); } } REP(i,h) REP(j,w) if(dp[hsh[id][id+1]][i][j]==-1) dp[hsh[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) hsh[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[hsh[i][j]][y][x]=INF; REP(k,len-1){ int div=i+k+1; dp[hsh[i][j]][y][x]=min(dp[hsh[i][j]][y][x],dp[hsh[i][div]][y][x]+dp[hsh[div][j]][y][x]); } if(dp[hsh[i][j]][y][x]!=INF){ used.pb(dp[hsh[i][j]][y][x]); posByCost[dp[hsh[i][j]][y][x]].pb(mp(y,x)); mini=min(mini,mp(dp[hsh[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[hsh[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[hsh[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[hsh[i][j]][nxt.fr][nxt.sc]<=c+1) continue; dp[hsh[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[hsh[0][n]][i][j]); if(res==INF) res=-1; printf("%d\n",res); return 0; }

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d%d%d",&n,&w,&h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:86:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  REP(i,h) scanf("%s",buf[i]);
      |           ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...