Submission #40009

#	Time	Username	Problem	Language	Result	Execution time	Memory
40009		comtalyst	Soccer (JOI17_soccer)	C++14	100 / 100	439 ms	29976 KiB

soccer

/*
 *	Task: JOI17_SOCCER
 *	Lang: C/C++11
 *	Author: comtalyst
 *	Site: oj.uz
 *	Last Update: 25/1/2018
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
SOLUTION VIEWED
----------------------------
Learned : 
Bugs found & solved :
Optimizations :
----------------------------
[0] = moving with ball
[1] = vertical kick
[2] = horizontal kick
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (long)(1e16+5)
#define MIN (long)(-1e16-5)
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

long nearest[510][510],R,C,sp[510][510][5];
pair<long,long> dr[]={{1,0},{0,1},{-1,0},{0,-1}},p[100005];
bool valid1(long x,long y,long d){
	if(x < 1 || y < 1 || x > R || y > C){
		return false;
	}
	if(nearest[x][y] == -1 || nearest[x][y] > d){
		nearest[x][y] = d;
		return true;
	}
	return false;
}
bool valid2(long x,long y,long t,long d){
	if(x < 1 || y < 1 || x > R || y > C){
		return false;
	}
	if(sp[x][y][t] == -1 || sp[x][y][t] > d){
		sp[x][y][t] = d;
		return true;
	}
	return false;
}


main(){
	long t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
	queue<tuple<long,long,long>> q;
	pqueue<tuple<long,long,long,long>> pq;
	memset(nearest,-1,sizeof nearest);
	memset(sp,-1,sizeof sp);
	
	scanf("%lld %lld",&R,&C);
	R += 5;
	C += 5;
	scanf("%lld %lld %lld",&a,&b,&c);
	scanf("%lld",&n);
	for(i = 1; i <= n; i++){
		scanf("%lld %lld",&p[i].x,&p[i].y);
		p[i].x++;
		p[i].y++;
		nearest[p[i].x][p[i].y] = 0;
		q.emplace(0,p[i].x,p[i].y);
	}
	while(!q.empty()){
		tie(d,x,y) = q.front();
		q.pop();
		if(d > nearest[x][y]){
			continue;
		}
		for(i = 0; i < 4; i++){
			nx = x + dr[i].x;
			ny = y + dr[i].y;
			if(valid1(nx,ny,d+1)){
				q.emplace(nearest[nx][ny],nx,ny);
			}
		}
	}
	sp[p[1].x][p[1].y][0] = 0;
	pq.emplace(0,p[1].x,p[1].y,0);
	while(!pq.empty()){
		tie(d,x,y,t) = pq.top();
		pq.pop();
		d = -d;
		if(d > sp[x][y][t]){
			continue;
		}
		if(!t){							// moving with ball
			for(i = 0; i < 4; i++){								// continue moving
				nx = x + dr[i].x;
				ny = y + dr[i].y;
				if(valid2(nx,ny,0,d+c)){
					pq.emplace(-sp[nx][ny][0],nx,ny,0);
				}
			}
			if(valid2(x,y,1,d+b)){								// starts horizontal kick
				pq.emplace(-sp[x][y][1],x,y,1);
			}
			if(valid2(x,y,2,d+b)){								// starts vertical kick
				pq.emplace(-sp[x][y][2],x,y,2);
			}
		}
		else if(t == 1){				// horizontally kicking
			for(i = 1; i < 4; i+=2){							// continue kicking
				nx = x + dr[i].x;
				ny = y + dr[i].y;
//				printf("> %lld %lld = %lld\n",nx,ny,d+a);
				if(valid2(nx,ny,1,d+a)){
					pq.emplace(-sp[nx][ny][1],nx,ny,1);
				}
			}
			if(valid2(x,y,0,d+nearest[x][y]*c)){					// stop the ball and calls nearest teammate to catch it
				pq.emplace(-sp[x][y][0],x,y,0);
			}
		}
		else{							// vertically kicking
			for(i = 0; i < 4; i+=2){							// continue kicking
				nx = x + dr[i].x;
				ny = y + dr[i].y;
				if(valid2(nx,ny,2,d+a)){
					pq.emplace(-sp[nx][ny][2],nx,ny,2);
				}
			}
			if(valid2(x,y,0,d+nearest[x][y]*c)){					// stop the ball and calls nearest teammate to catch it
				pq.emplace(-sp[x][y][0],x,y,0);
			}
		}
	}
	if(sp[p[n].x][p[n].y][0] == -1) sp[p[n].x][p[n].y][0] = MAX;
	if(sp[p[n].x][p[n].y][1] == -1) sp[p[n].x][p[n].y][1] = MAX;
	if(sp[p[n].x][p[n].y][2] == -1) sp[p[n].x][p[n].y][2] = MAX;
	printf("%lld\n",min(sp[p[n].x][p[n].y][0],min(sp[p[n].x][p[n].y][1],sp[p[n].x][p[n].y][2])));

	return 0;	
}

Compilation message (stderr)

soccer.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
soccer.cpp: In function 'int main()':
soccer.cpp:66:11: warning: unused variable 'j' [-Wunused-variable]
  long t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
           ^
soccer.cpp:66:13: warning: unused variable 'k' [-Wunused-variable]
  long t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
             ^
soccer.cpp:66:17: warning: unused variable 'm' [-Wunused-variable]
  long t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
                 ^
soccer.cpp:72:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&R,&C);
                          ^
soccer.cpp:75:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&a,&b,&c);
                                  ^
soccer.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
soccer.cpp:78:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&p[i].x,&p[i].y);
                                     ^

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65