Submission #49330

#TimeUsernameProblemLanguageResultExecution timeMemory
49330hamzqq9Robots (APIO13_robots)C++14
30 / 100
136 ms61276 KiB
#include<bits/stdc++.h> #define lf double #define ll long long #define cc pair<char,char> #define ull unsigned ll #define ii pair<int,int> #define li pair<ll,int> #define iii pair<ii,int> #define iiii pair<ii,ii> #define iiii2 pair<int,iii> #define lii pair<ll,ii> #define lolo pair<ll,ll> #define heap priority_queue #define mp make_pair #define st first #define nd second #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define all(x) x.begin(),x.end() #define len(x) strlen(x) #define sz(x) (int) x.size() #define orta ((bas+son)/2) #define min3(x,y,z) min(min(x,y),z) #define max3(x,y,z) max(max(x,y),z) #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define MOD 100000000 #define inf 1050000000 #define N 505 #define LOG 20 #define magic 100 #define KOK 250 #define EPS 0.0025 #define pw(x) (1<<(x)) #define PI 3.1415926535 using namespace std; int masks,ans=-1,n,w,h; int tut[526],maskof[55]; ii place[50]; int dp[50]; ii go[N][N][4]; int cost[50][N][N]; bool vis[50][N][N],gov[N][N][4]; int way[4][2]={1,0,0,-1,-1,0,0,1}; char a[N][N]; void bfs(ii start,int state) { queue<iii> q; q.push({start,0}); while(!q.empty()) { iii now=q.front(); q.pop(); if(vis[state][now.st.st][now.st.nd]) continue ; vis[state][now.st.st][now.st.nd]=true; cost[state][now.st.st][now.st.nd]=now.nd; for(int i=0;i<4;i++) { q.push({go[now.st.st][now.st.nd][i],now.nd+1}); } } } void process(int mask) { int alt=(mask&-mask); for(int msk=mask-alt;msk>0;alt+=(msk&-msk),msk-=(msk&-msk)) { if(dp[tut[msk]]==inf || dp[tut[alt]]==inf) continue ; ii p1=place[tut[msk]]; ii p2=place[tut[alt]]; bfs(p1,tut[msk]); bfs(p2,tut[alt]); int merge=inf; ii plc; for(int i=1;i<=h;i++) { for(int j=1;j<=w;j++) { if(merge>cost[tut[msk]][i][j]+cost[tut[alt]][i][j]) { merge=cost[tut[msk]][i][j]+cost[tut[alt]][i][j]; plc={i,j}; } } } if(dp[tut[mask]]>merge+dp[tut[msk]]+dp[tut[alt]]) { dp[tut[mask]]=merge+dp[tut[msk]]+dp[tut[alt]]; place[tut[mask]]=plc; } } } ii dfs(int x,int y,int dir) { if(gov[x][y][dir]) return go[x][y][dir]; gov[x][y][dir]=1; int todir=dir; if(a[x][y]=='A') todir=(dir-1+4)%4; else if(a[x][y]=='C') todir=(dir+1)%4; int tox=x+way[todir][0]; int toy=y+way[todir][1]; if(a[tox][toy]=='x' || tox==0 || toy==0 || tox>h || toy>w) return go[x][y][dir]={x,y}; return go[x][y][dir]=dfs(tox,toy,todir); } int main() { // freopen("input.txt","r",stdin); scanf("%d %d %d",&n,&w,&h); for(int i=1;i<=n;i++) { for(int s=1;s<=n-i+1;s++) { int mask=0; for(int j=s;j<=s+i-1;j++) { mask|=pw(j-1); } tut[mask]=++masks; maskof[masks]=mask; } } for(int i=1;i<=masks;i++) { dp[i]=inf; } for(int i=0;i<50;i++) { for(int j=0;j<N;j++) { for(int k=0;k<N;k++) { cost[i][j][k]=inf; } } } for(int i=1;i<=h;i++) { scanf("%s",a[i]+1); for(int j=1;j<=w;j++) { if(a[i][j]>='1' && a[i][j]<='9') { place[tut[pw(a[i][j]-'1')]]={i,j}; dp[tut[pw(a[i][j]-'1')]]=0; a[i][j]='.'; } } } for(int i=1;i<=h;i++) { for(int j=1;j<=w;j++) { if(a[i][j]=='x') continue ; for(int dir=0;dir<4;dir++) { if(!gov[i][j][dir]) { dfs(i,j,dir); } } } } for(int i=1;i<=masks;i++) { process(maskof[i]); } if(dp[masks]!=inf) ans=dp[masks]; printf("%d",ans); }

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:150:7: 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:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",a[i]+1);
   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...