Submission #83825

#	Time	Username	Problem	Language	Result	Execution time	Memory
83825		ekrem	Soccer (JOI17_soccer)	C++98	5 / 100	252 ms	32816 KiB

soccer

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000000000000007
#define ek(a,b,c,d,e) mp(a,mp(mp(b,c),mp(d,e)))
#define N 505
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef pair < ii , ii > i4;

int n, m, k, x[100005], y[100005];
ll a, b, c, ans = inf, d[N][N][4][4];
int o[] = {0, 0, 1, -1};
int p[] = {1, -1, 0, 0};
priority_queue < pair < ll , i4 > > q;

bool git(int i, int j){return !(i < 1 or j < 1 or i > n or j > m);}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(d, 60, sizeof d);
	scanf("%d %d %lld %lld %lld %d",&n ,&m ,&a ,&b ,&c ,&k);n++;m++;
	scanf("%d %d",x + 1, y + 1);x[1]++;y[1]++;
	d[x[1]][y[1]][3][0] = 0;
	q.push(ek(0, x[1], y[1], 3, 0));
	for(int i = 2; i <= k; i++){
		scanf("%d %d",x + i, y + i);x[i]++;y[i]++;
		d[x[i]][y[i]][2][0] = 0;
		q.push(ek(0, x[i], y[i], 2, 0));
	}
	while(!q.empty()){
		pair < ll , i4 > tp = q.top();q.pop();
		int x = tp.nd.st.st, y = tp.nd.st.nd, dur = tp.nd.nd.st, yon = tp.nd.nd.nd;
		if(dur == 0){
			if(d[x][y][1][0] > d[x][y][0][yon]){//Topu durdur.
				d[x][y][1][0] = d[x][y][0][yon];
				q.push(ek(-d[x][y][1][0], x, y, 1, 0));
			}
			if(git(x + o[yon], y + p[yon]) and d[x + o[yon]][y + p[yon]][0][yon] > d[x][y][0][yon] + a){
				d[x + o[yon]][y + p[yon]][0][yon] = d[x][y][0][yon] + a;
				q.push(ek(-d[x + o[yon]][y + p[yon]][0][yon], x + o[yon], y + p[yon], 0, yon));
			}
		}
		if(dur == 1){
			if(d[x][y][3][0] > d[x][y][1][0] + d[x][y][2][0]){
				d[x][y][3][0] = d[x][y][1][0] + d[x][y][2][0];
				q.push(ek(-d[x][y][3][0], x, y, 3, 0));
			}
		}
		if(dur == 2){
			if(d[x][y][3][0] > d[x][y][1][0] + d[x][y][2][0]){
				d[x][y][3][0] = d[x][y][1][0] + d[x][y][2][0];
				q.push(ek(-d[x][y][3][0], x, y, 3, 0));
			}
			for(int i = 0; i < 4; i++){
				if(git(x + o[i], y + p[i]) and d[x + o[i]][y + p[i]][2][0] > d[x][y][2][0] + c){
					d[x + o[i]][y + p[i]][2][0] = d[x][y][2][0] + c;
					q.push(ek(-d[x + o[yon]][y + p[yon]][2][0], x + o[yon], y + p[yon], 2, 0));
				}
			}
		}
		if(dur == 3){
			for(int i = 0; i < 4; i++){
				if(git(x + o[i], y + p[i]) and d[x + o[i]][y + p[i]][3][0] > d[x][y][3][0] + c){
					d[x + o[i]][y + p[i]][3][0] = d[x][y][3][0] + c;
					q.push(ek(-d[x + o[yon]][y + p[yon]][3][0], x + o[yon], y + p[yon], 3, 0));
				}
			}
			for(int i = 0; i < 4; i++){
				if(d[x][y][0][i] > d[x][y][3][0] + b){
					d[x][y][0][i] = d[x][y][3][0] + b;
					q.push(ek(-d[x][y][0][i], x, y, 0, i));
				}
			}
			if(d[x][y][1][0] > d[x][y][3][0]){
				d[x][y][1][0] = d[x][y][3][0];
				q.push(ek(-d[x][y][1][0], x, y, 1, 0));
			}
			if(d[x][y][2][0] > d[x][y][3][0]){
				d[x][y][2][0] = d[x][y][3][0];
				q.push(ek(-d[x][y][2][0], x, y, 2, 0));
			}
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			ans = min(ans, abs(x[k] - i)*c + abs(y[k] - j)*c + d[i][j][1][0]);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld %lld %lld %d",&n ,&m ,&a ,&b ,&c ,&k);n++;m++;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",x + 1, y + 1);x[1]++;y[1]++;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",x + i, y + i);x[i]++;y[i]++;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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