oj.uz

Submission #49330

# Submission time Handle Problem Language Result Execution time Memory
49330 2018-05-26T04:17:56 Z hamzqq9 Robots (APIO13_robots) C++14
30 / 100
 136 ms 61276 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 100000000
#define inf 1050000000
#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 masks,ans=-1,n,w,h;
int tut[526],maskof[55];
ii place[50];
int dp[50];
ii go[N][N][4];
int cost[50][N][N];
bool vis[50][N][N],gov[N][N][4];
int way[4][2]={1,0,0,-1,-1,0,0,1};
char a[N][N];

void bfs(ii start,int state) {

	queue<iii> q;

	q.push({start,0});

	while(!q.empty()) {

		iii now=q.front();

		q.pop();

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

		vis[state][now.st.st][now.st.nd]=true;

		cost[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});

		}

	}

}
 
void process(int mask) {

	int alt=(mask&-mask);

	for(int msk=mask-alt;msk>0;alt+=(msk&-msk),msk-=(msk&-msk)) {

		if(dp[tut[msk]]==inf || dp[tut[alt]]==inf) continue ;

		ii p1=place[tut[msk]];

		ii p2=place[tut[alt]];

		bfs(p1,tut[msk]);

		bfs(p2,tut[alt]);

		int merge=inf;

		ii plc;

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

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

				if(merge>cost[tut[msk]][i][j]+cost[tut[alt]][i][j]) {

					merge=cost[tut[msk]][i][j]+cost[tut[alt]][i][j];

					plc={i,j};

				}

			}

		}

		if(dp[tut[mask]]>merge+dp[tut[msk]]+dp[tut[alt]]) {

			dp[tut[mask]]=merge+dp[tut[msk]]+dp[tut[alt]];

			place[tut[mask]]=plc;

		}

	}

}

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

			int mask=0;

			for(int j=s;j<=s+i-1;j++) {

				mask|=pw(j-1);

			}

			tut[mask]=++masks;
			maskof[masks]=mask;

		}

	}

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

		dp[i]=inf;


	}
	
	for(int i=0;i<50;i++) {

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

			for(int k=0;k<N;k++) {

				cost[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[tut[pw(a[i][j]-'1')]]={i,j};
				dp[tut[pw(a[i][j]-'1')]]=0;
				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<=masks;i++) {

		process(maskof[i]);

	}

	if(dp[masks]!=inf) ans=dp[masks];

	printf("%d",ans);
  
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:150: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:194: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 50 ms 50424 KB Output is correct
2 Correct 54 ms 50424 KB Output is correct
3 Correct 136 ms 50424 KB Output is correct
4 Correct 43 ms 50580 KB Output is correct
5 Correct 42 ms 50580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 50424 KB Output is correct
2 Correct 54 ms 50424 KB Output is correct
3 Correct 136 ms 50424 KB Output is correct
4 Correct 43 ms 50580 KB Output is correct
5 Correct 42 ms 50580 KB Output is correct
6 Correct 39 ms 50580 KB Output is correct
7 Correct 47 ms 50680 KB Output is correct
8 Correct 50 ms 50684 KB Output is correct
9 Correct 43 ms 50684 KB Output is correct
10 Correct 43 ms 50728 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 50424 KB Output is correct
2 Correct 54 ms 50424 KB Output is correct
3 Correct 136 ms 50424 KB Output is correct
4 Correct 43 ms 50580 KB Output is correct
5 Correct 42 ms 50580 KB Output is correct
6 Correct 39 ms 50580 KB Output is correct
7 Correct 47 ms 50680 KB Output is correct
8 Correct 50 ms 50684 KB Output is correct
9 Correct 43 ms 50684 KB Output is correct
10 Correct 43 ms 50728 KB Output is correct
11 Incorrect 112 ms 61276 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 50424 KB Output is correct
2 Correct 54 ms 50424 KB Output is correct
3 Correct 136 ms 50424 KB Output is correct
4 Correct 43 ms 50580 KB Output is correct
5 Correct 42 ms 50580 KB Output is correct
6 Correct 39 ms 50580 KB Output is correct
7 Correct 47 ms 50680 KB Output is correct
8 Correct 50 ms 50684 KB Output is correct
9 Correct 43 ms 50684 KB Output is correct
10 Correct 43 ms 50728 KB Output is correct
11 Incorrect 112 ms 61276 KB Output isn't correct
12 Halted 0 ms 0 KB -