Submission #934816

#	Time	Username	Problem	Language	Result	Execution time	Memory
934816		8pete8	Robots (APIO13_robots)	C++17	30 / 100	414 ms	92620 KiB

robots

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
const int mod=1e9+7,mxn=505,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}	 
pii pos[10];
char grid[mxn+10][mxn+10];
int n,h,w;
int dist[mxn*mxn+10],go[mxn+10][mxn+10][4];
vector<int> dp[10][10];
vector<int>adj[mxn*mxn+10];
int get(int x,int y){
	return y+((x-1)*w);
}
int u[4]={1,0,-1,0},r[4]={0,-1,0,1};
bool valid(int x,int y){
	if(x<=0||x>h||y<=0||y>w)return false;
	if(grid[x][y]=='x')return false;
	return true;
}
struct node{
	int pos,stp;
	bool operator<(const node o)const{return stp>o.stp;}
};
void move(vector<int>&v){
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=1;i<=v.size();i++)if(v[i]!=inf)pq.push({v[i],i});
	while(!pq.empty()){
		int cur=pq.top().s,cost=pq.top().f;
		pq.pop();
		if(cost>v[cur])continue;
		for(auto i:adj[cur]){if(v[i]>v[cur]+1){
				v[i]=v[cur]+1;
				pq.push({v[i],i});
			}
		}
	}
	return;
}
int dp2[10][mxn*mxn+10];
int getnx(int x,int y,int di){
	if(grid[x][y]=='A')di--;
	else if(grid[x][y]=='C')di++;
	di=(di+4)%4;
	if(go[x][y][di])return go[x][y][di];
	int nx=x+u[di],ny=y+r[di];
	if(valid(nx,ny))return go[x][y][di]=getnx(nx,ny,di);
	return go[x][y][di]=get(x,y);
}
//41->21->11
void print(int i,int j){
	for(int x=1;x<=h;x++){
		for(int y=1;y<=w;y++)cout<<((dp[i][j][get(x,y)]==inf)?-1:dp[i][j][get(x,y)])<<" ";
		cout<<'\n';
	}
	cout<<'\n';
}
int32_t main(){
	fastio
	cin>>n>>w>>h;
	int ans=inf;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j].resize(h*(w+1),inf);
	for(int i=1;i<=n;i++)for(int x=1;x<=h*w;x++)dp2[i][x]=inf;
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
		cin>>grid[i][j];
		if(grid[i][j]>='1'&&grid[i][j]<='9')pos[grid[i][j]-'0']={i,j};
	}
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)for(int k=0;k<4;k++)adj[get(i,j)].pb(getnx(i,j,k));
	for(int i=1;i<=n;i++){
		dp[i][i][get(pos[i].f,pos[i].s)]=0;
		move(dp[i][i]);
		//print(i,i);
	}
	for(int i=1;i<=n;i++)for(int j=i-1;j>=1;j--){
		for(int x=1;x<=h*w;x++){
				dp[i][j][x]=min(inf,dp[i][j+1][x]+dp[j][j][x]);
		}
		move(dp[i][j]);
	}
	for(int x=1;x<=h*w;x++){
		for(int i=1;i<=n;i++){
			for(int j=i;j>=1;j--)dp2[i][x]=min(dp2[i][x],dp[i][j][x]+dp2[j-1][x]);
		}
	}/*
	for(int x=1;x<=h;x++){
		for(int y=1;y<=w;y++)cout<<((dp2[n][get(x,y)]==inf)?-1:dp2[n][get(x,y)])<<" ";
		cout<<'\n';
	}
	cout<<'\n';
	*/
	for(int x=1;x<=h*w;x++)ans=min(ans,dp2[n][x]);
	cout<<((ans==inf)?-1:ans);
	/*
	for(int i=1;i<=2;i++){
		
		//break;
	}*/
	
	//for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)ans=min(ans,dp[i][j][n]);
	/*
	1 2 3
 
 
	*/
}

Compilation message (stderr)

robots.cpp: In function 'void move(std::vector<long long int>&)':
robots.cpp:61:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=1;i<=v.size();i++)if(v[i]!=inf)pq.push({v[i],i});
      |              ~^~~~~~~~~~
robots.cpp: In function 'void setIO(std::string)':
robots.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40