Submission #49331

#TimeUsernameProblemLanguageResultExecution timeMemory
49331hamzqq9Robots (APIO13_robots)C++14
30 / 100
1573 ms70752 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 1000000000 #define inf 1000000000 #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 ans=inf,n,w,h,tot; int dp[50][N][N],tut[10][10]; ii go[N][N][4],place[10]; bool gov[N][N][4],vis[50][N][N]; int way[4][2]={1,0,0,-1,-1,0,0,1}; char a[N][N]; struct cmp { bool operator () (iii x,iii y) { return (x.nd>y.nd); } } ; void sp(vector<iii> start,int state) { heap<iii,vector<iii>,cmp> q; for(int i=0;i<sz(start);i++) q.push(start[i]); while(!q.empty()) { iii now=q.top(); q.pop(); if(vis[state][now.st.st][now.st.nd]) continue ; vis[state][now.st.st][now.st.nd]=true; dp[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}); } } } 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++) { tut[s][s+i-1]=++tot; } } for(int i=0;i<50;i++) { for(int j=0;j<N;j++) { for(int k=0;k<N;k++) { dp[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[a[i][j]-'0']={i,j}; 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<=n;i++) { vector<iii> res; res.pb({place[i],0}); sp(res,tut[i][i]); } for(int l=2;l<=n;l++) { for(int s=1;s<=n-l+1;s++) { int now=tut[s][s+l-1]; int e=s+l-1; for(int e1=s;e1<e;e1++) { int now1=tut[s][e1]; int now2=tut[e1+1][e]; for(int i=1;i<=h;i++) { for(int j=1;j<=w;j++) { dp[now][i][j]=min(dp[now][i][j],dp[now1][i][j]+dp[now2][i][j]); } } } vector<iii> res; for(int i=1;i<=h;i++) { for(int j=1;j<=w;j++) { res.pb({{i,j},dp[now][i][j]}); } } sp(res,now); } } for(int i=1;i<=h;i++) { for(int j=1;j<=w;j++) { ans=min(ans,dp[tut[1][n]][i][j]); //printf("%d %d %d\n",i,j,dp[tut[1][n]][i][j]); } } if(ans==inf) ans=-1; printf("%d",ans); }

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:109: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:137: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...