Submission #91254

#	Time	Username	Problem	Language	Result	Execution time	Memory
91254		Dat160601	Soccer (JOI17_soccer)	C++17	100 / 100	690 ms	62304 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;
typedef pair <pair <long long, int> , pii> pli;

int n, m, sz, x[100007], y[100007];
long long A, B, C, ans = 0, dist[507][507][5], init[507][507];
int px[] = {+1, -1, 0, 0};
int py[] = {0, 0, +1, -1};
queue < pair <int, int> > q;
priority_queue < pli, vector <pli>, greater <pli> > pr;

int main(){
	scanf("%d %d", &n, &m);
	n ++, m ++;
	scanf("%lld %lld %lld", &A, &B, &C);
	scanf("%d", &sz);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			init[i][j] = 1e9;
			for(int k = 0; k < 5; k++){
				dist[i][j][k] = 1e16;
			}
		}
	}
	for(int i = 1; i <= sz; i++){
		scanf("%d %d", &x[i], &y[i]);
		x[i] ++, y[i] ++;
		q.push(mp(x[i], y[i]));
		init[x[i]][y[i]] = 0;
	}
	while(!q.empty()){
		int cx = q.front().fi, cy = q.front().se;
		q.pop();
		for(int dir = 0; dir < 4; dir++){
			int nx = cx + px[dir], ny = cy + py[dir];
			if(nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
			if(init[nx][ny] > init[cx][cy] + 1){
				init[nx][ny] = init[cx][cy] + 1;
				q.push(mp(nx, ny));
			}
		}
	}
	/*for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout << init[i][j] << " ";
		}
		cout << endl;
	}*/
	dist[x[1]][y[1]][4] = 0;
	pr.push(mp(mp(0, 4), mp(x[1], y[1])));
	while(!pr.empty()){
		int cx = pr.top().se.fi;
		int cy = pr.top().se.se;
		int type = pr.top().fi.se;
		long long val = pr.top().fi.fi;
		pr.pop();
		if(dist[cx][cy][type] != val) continue;
		if(cx == x[sz] && cy == y[sz]){
			printf("%lld", val);
			return 0;
			//ans = min(ans, val);
		}
		if(type < 4){
			int nx = cx + px[type], ny = cy + py[type];
			if(nx > 0 && nx <= n && ny > 0 && ny <= m && dist[nx][ny][type] > val + A){
				dist[nx][ny][type] = val + A;
				pr.push(mp(mp(dist[nx][ny][type], type), mp(nx, ny)));
			}
			val += C * 1LL * init[cx][cy];
		}
		for(int dir = 0; dir < 4; dir++){
			int nx = cx + px[dir], ny = cy + py[dir];
			if(nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
			if(dist[nx][ny][4] > val + C){
				dist[nx][ny][4] = val + C;
				pr.push(mp(mp(dist[nx][ny][4], 4), mp(nx, ny)));
			}
			if(dist[nx][ny][dir] > val + A + B){
				dist[nx][ny][dir] = val + A + B;
				pr.push(mp(mp(dist[nx][ny][dir], dir), mp(nx, ny)));
			}
		}
	}
	printf("~~This should not happen~~");
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
soccer.cpp:20:7: 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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &sz);
  ~~~~~^~~~~~~~~~~
soccer.cpp:31: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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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