oj.uz

Submission #49331

# Submission time Handle Problem Language Result Execution time Memory
49331 2018-05-26T05:31:09 Z hamzqq9 Robots (APIO13_robots) C++14
30 / 100
 1500 ms 70752 KB 
#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

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);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 50168 KB Output is correct
2 Correct 38 ms 50276 KB Output is correct
3 Correct 38 ms 50356 KB Output is correct
4 Correct 38 ms 50356 KB Output is correct
5 Correct 38 ms 50496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 50168 KB Output is correct
2 Correct 38 ms 50276 KB Output is correct
3 Correct 38 ms 50356 KB Output is correct
4 Correct 38 ms 50356 KB Output is correct
5 Correct 38 ms 50496 KB Output is correct
6 Correct 38 ms 50496 KB Output is correct
7 Correct 38 ms 50584 KB Output is correct
8 Correct 38 ms 50584 KB Output is correct
9 Correct 39 ms 50584 KB Output is correct
10 Correct 40 ms 50684 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 50168 KB Output is correct
2 Correct 38 ms 50276 KB Output is correct
3 Correct 38 ms 50356 KB Output is correct
4 Correct 38 ms 50356 KB Output is correct
5 Correct 38 ms 50496 KB Output is correct
6 Correct 38 ms 50496 KB Output is correct
7 Correct 38 ms 50584 KB Output is correct
8 Correct 38 ms 50584 KB Output is correct
9 Correct 39 ms 50584 KB Output is correct
10 Correct 40 ms 50684 KB Output is correct
11 Execution timed out 1573 ms 70752 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 50168 KB Output is correct
2 Correct 38 ms 50276 KB Output is correct
3 Correct 38 ms 50356 KB Output is correct
4 Correct 38 ms 50356 KB Output is correct
5 Correct 38 ms 50496 KB Output is correct
6 Correct 38 ms 50496 KB Output is correct
7 Correct 38 ms 50584 KB Output is correct
8 Correct 38 ms 50584 KB Output is correct
9 Correct 39 ms 50584 KB Output is correct
10 Correct 40 ms 50684 KB Output is correct
11 Execution timed out 1573 ms 70752 KB Time limit exceeded
12 Halted 0 ms 0 KB -