oj.uz

Submission #934818

# Submission time Handle Problem Language Result Execution time Memory
934818 2024-02-28T04:39:34 Z 8pete8 Robots (APIO13_robots) C++17
30 / 100
 1500 ms 92080 KB 
#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]);
	}
	for(int x=1;x<=h*w;x++)for(int sz=2;sz<=n;sz++){
		for(int l=1,r=sz;r<=n;l++,r++){
			for(int mid=l;mid<r;mid++)dp[l][r][x]=min(dp[l][r][x],dp[l][mid][x]+dp[mid+1][r][x]);
			move(dp[l][r]);
		}
	}
	for(int x=1;x<=h*w;x++)ans=min(ans,dp[1][n][x]);
	cout<<((ans==inf)?-1:ans);
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 4 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 4 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Execution timed out 1526 ms 92080 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 4 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Execution timed out 1526 ms 92080 KB Time limit exceeded
12 Halted 0 ms 0 KB -