oj.uz

Submission #40009

# Submission time Handle Problem Language Result Execution time Memory
40009 2018-01-25T08:28:02 Z comtalyst Soccer (JOI17_soccer) C++14
100 / 100
 439 ms 29976 KB 
/*
 *	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

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

# Verdict Execution time Memory Grader output
1 Correct 74 ms 18944 KB Output is correct
2 Correct 4 ms 15916 KB Output is correct
3 Correct 370 ms 28168 KB Output is correct
4 Correct 389 ms 28168 KB Output is correct
5 Correct 68 ms 15920 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 28204 KB Output is correct
2 Correct 392 ms 28204 KB Output is correct
3 Correct 286 ms 28192 KB Output is correct
4 Correct 236 ms 28172 KB Output is correct
5 Correct 291 ms 28204 KB Output is correct
6 Correct 261 ms 28176 KB Output is correct
7 Correct 379 ms 28512 KB Output is correct
8 Correct 370 ms 28340 KB Output is correct
9 Correct 390 ms 28516 KB Output is correct
10 Correct 62 ms 19112 KB Output is correct
11 Correct 389 ms 28468 KB Output is correct
12 Correct 384 ms 28204 KB Output is correct
13 Correct 197 ms 28176 KB Output is correct
14 Correct 369 ms 28468 KB Output is correct
15 Correct 297 ms 28468 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 18944 KB Output is correct
2 Correct 4 ms 15916 KB Output is correct
3 Correct 370 ms 28168 KB Output is correct
4 Correct 389 ms 28168 KB Output is correct
5 Correct 68 ms 15920 KB Output is correct
6 Correct 396 ms 28204 KB Output is correct
7 Correct 392 ms 28204 KB Output is correct
8 Correct 286 ms 28192 KB Output is correct
9 Correct 236 ms 28172 KB Output is correct
10 Correct 291 ms 28204 KB Output is correct
11 Correct 261 ms 28176 KB Output is correct
12 Correct 379 ms 28512 KB Output is correct
13 Correct 370 ms 28340 KB Output is correct
14 Correct 390 ms 28516 KB Output is correct
15 Correct 62 ms 19112 KB Output is correct
16 Correct 389 ms 28468 KB Output is correct
17 Correct 384 ms 28204 KB Output is correct
18 Correct 197 ms 28176 KB Output is correct
19 Correct 369 ms 28468 KB Output is correct
20 Correct 297 ms 28468 KB Output is correct
21 Correct 68 ms 16288 KB Output is correct
22 Correct 395 ms 28204 KB Output is correct
23 Correct 368 ms 22184 KB Output is correct
24 Correct 409 ms 22364 KB Output is correct
25 Correct 375 ms 28204 KB Output is correct
26 Correct 391 ms 28536 KB Output is correct
27 Correct 293 ms 19020 KB Output is correct
28 Correct 253 ms 19428 KB Output is correct
29 Correct 373 ms 23832 KB Output is correct
30 Correct 241 ms 18472 KB Output is correct
31 Correct 360 ms 28504 KB Output is correct
32 Correct 435 ms 29976 KB Output is correct
33 Correct 332 ms 28176 KB Output is correct
34 Correct 439 ms 28524 KB Output is correct
35 Correct 200 ms 18340 KB Output is correct