oj.uz

Submission #49332

# Submission time Handle Problem Language Result Execution time Memory
49332 2018-05-26T06:03:16 Z hamzqq9 Robots (APIO13_robots) C++14
100 / 100
 551 ms 109372 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];
vector<ii> sh[N*N];

void sp(int state) {

	int mn=inf;

	for(int i=1;i<=h;i++) {

		for(int j=1;j<=w;j++) {

			if(dp[state][i][j]==inf) continue ;

			if(dp[state][i][j]<mn) mn=dp[state][i][j];

			sh[dp[state][i][j]].pb({i,j});

		}

	}

	for(int i=mn;i<N*N;i++) {

		while(sz(sh[i])) {

			ii pl=sh[i].back();

			sh[i].ppb();

			if(vis[state][pl.st][pl.nd]) continue ;

			vis[state][pl.st][pl.nd]=1;

			dp[state][pl.st][pl.nd]=i;

			for(int j=0;j<4;j++) {

				ii to=go[pl.st][pl.nd][j];

				if(vis[state][to.st][to.nd]) continue ;

				sh[i+1].pb(to);

			}

		}

	}

}

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') {

				dp[tut[a[i][j]-'0'][a[i][j]-'0']][i][j]=0;
				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++) {

		sp(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]);

					}

				}

			}

			sp(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:120: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:148: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 51 ms 56184 KB Output is correct
2 Correct 49 ms 56292 KB Output is correct
3 Correct 46 ms 56328 KB Output is correct
4 Correct 48 ms 56344 KB Output is correct
5 Correct 53 ms 56344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56184 KB Output is correct
2 Correct 49 ms 56292 KB Output is correct
3 Correct 46 ms 56328 KB Output is correct
4 Correct 48 ms 56344 KB Output is correct
5 Correct 53 ms 56344 KB Output is correct
6 Correct 53 ms 56392 KB Output is correct
7 Correct 52 ms 56404 KB Output is correct
8 Correct 46 ms 56480 KB Output is correct
9 Correct 53 ms 56480 KB Output is correct
10 Correct 48 ms 56480 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56184 KB Output is correct
2 Correct 49 ms 56292 KB Output is correct
3 Correct 46 ms 56328 KB Output is correct
4 Correct 48 ms 56344 KB Output is correct
5 Correct 53 ms 56344 KB Output is correct
6 Correct 53 ms 56392 KB Output is correct
7 Correct 52 ms 56404 KB Output is correct
8 Correct 46 ms 56480 KB Output is correct
9 Correct 53 ms 56480 KB Output is correct
10 Correct 48 ms 56480 KB Output is correct
11 Correct 177 ms 72848 KB Output is correct
12 Correct 64 ms 72848 KB Output is correct
13 Correct 108 ms 72848 KB Output is correct
14 Correct 256 ms 76784 KB Output is correct
15 Correct 130 ms 76784 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56184 KB Output is correct
2 Correct 49 ms 56292 KB Output is correct
3 Correct 46 ms 56328 KB Output is correct
4 Correct 48 ms 56344 KB Output is correct
5 Correct 53 ms 56344 KB Output is correct
6 Correct 53 ms 56392 KB Output is correct
7 Correct 52 ms 56404 KB Output is correct
8 Correct 46 ms 56480 KB Output is correct
9 Correct 53 ms 56480 KB Output is correct
10 Correct 48 ms 56480 KB Output is correct
11 Correct 177 ms 72848 KB Output is correct
12 Correct 64 ms 72848 KB Output is correct
13 Correct 108 ms 72848 KB Output is correct
14 Correct 256 ms 76784 KB Output is correct
15 Correct 130 ms 76784 KB Output is correct
16 Correct 186 ms 76784 KB Output is correct
17 Correct 551 ms 109372 KB Output is correct
18 Correct 180 ms 109372 KB Output is correct
19 Correct 188 ms 109372 KB Output is correct
20 Correct 428 ms 109372 KB Output is correct