oj.uz

Submission #292171

# Submission time Handle Problem Language Result Execution time Memory
292171 2020-09-06T13:20:48 Z Namnamseo Soccer (JOI17_soccer) C++17
100 / 100
 1362 ms 48200 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
typedef tuple<int,int,int> t3;
typedef pair<ll, t3> dijk_flg;
const ll inf=(1LL<<60);

int dx[]={0,1,0,-1,0};
int* dy=dx+1;

ll nearest[510][510];
pp player[100010];

int A, B, C;
int N;
int n, m;

void in(){
	read(n, m, A, B, C, N);
	for(int i=1; i<=N; ++i) read(player[i].x, player[i].y);
}

ll dplu[510][510];
ll dpld[510][510];
ll dpru[510][510];
ll dprd[510][510];

void find_nearest(){
	memset(dplu, 0x7f, sizeof(dplu));
	memset(dpld, 0x7f, sizeof(dpld));
	memset(dpru, 0x7f, sizeof(dpru));
	memset(dprd, 0x7f, sizeof(dprd));
	for(int i=1; i<=N; ++i){
		int x, y; tie(x, y) = player[i];
		dplu[x][y]=min(dplu[x][y], 0ll-x-y);
		dpld[x][y]=min(dpld[x][y], 0ll+x-y);
		dpru[x][y]=min(dpru[x][y], 0ll-x+y);
		dprd[x][y]=min(dprd[x][y], 0ll+x+y);
	}
	for(int i=0; i<=n; ++i) for(int j=0; j<=m; ++j)
		dplu[i][j]=min({dplu[i][j], i?dplu[i-1][j]:inf, j?dplu[i][j-1]:inf});
	for(int i=0; i<=n; ++i) for(int j=m; j>=0; --j)
		dpru[i][j]=min({dpru[i][j], i?dpru[i-1][j]:inf, dpru[i][j+1]});
	for(int i=n; i>=0; --i) for(int j=0; j<=m; ++j)
		dpld[i][j]=min({dpld[i][j], dpld[i+1][j], j?dpld[i][j-1]:inf});
	for(int i=n; i>=0; --i) for(int j=m; j>=0; --j)
		dprd[i][j]=min({dprd[i][j], dprd[i+1][j], dprd[i][j+1]});
	
	for(int i=0; i<=n; ++i) for(int j=0; j<=m; ++j){
		nearest[i][j] = inf;
		nearest[i][j]=min(nearest[i][j],+i+j + dplu[i][j]);
		nearest[i][j]=min(nearest[i][j],-i+j + dpld[i][j]);
		nearest[i][j]=min(nearest[i][j],+i-j + dpru[i][j]);
		nearest[i][j]=min(nearest[i][j],-i-j + dprd[i][j]);
		nearest[i][j] *= C;
	}
}

// 0   : stationary
// 1-4 : flying
// 5   : holding & moving

void populate_edge_list(int d, int x, int y, vector<pair<t3, ll>>& v){
	v.clear();
	if(d == 0){
		ll ne = nearest[x][y];
		v.eb(t3{1, x, y}, ne+B);
		v.eb(t3{2, x, y}, ne+B);
		v.eb(t3{3, x, y}, ne+B);
		v.eb(t3{4, x, y}, ne+B);
		v.eb(t3{5, x, y}, ne);
	} else if(1<=d && d<=4){
		int nx=x+dx[d-1], ny=y+dy[d-1];
		if(nx<=n && ny<=m && nx>=0 && ny>=0){
			v.eb(t3{d, nx, ny}, A);
		}
		v.eb(t3{0, x, y}, 0);
	} else {
		v.eb(t3{0, x, y}, 0);
		v.eb(t3{1, x, y}, B);
		v.eb(t3{2, x, y}, B);
		v.eb(t3{3, x, y}, B);
		v.eb(t3{4, x, y}, B);
		for(int d=0; d<4; ++d){
			int nx=x+dx[d], ny=y+dy[d];
			if(nx<=n && ny<=m && nx>=0 && ny>=0){
				v.eb(t3{5, nx, ny}, C);
			}
		}
	}
}

ll dist[6][510][510];

void dijk(){
	priority_queue<dijk_flg> pq;
	memset(dist, 0x7f, sizeof(dist));
	int sx, sy; tie(sx, sy) = player[1];
	int tx, ty; tie(tx, ty) = player[N];
	dist[0][sx][sy]=0;
	pq.emplace(0, t3{0, sx, sy});
	vector<pair<t3, ll>> edge_list;
	while(pq.size()){
		int ind, x, y;
		ll d;
		tie(ind, x, y) = pq.top().second;
		d = -pq.top().first;
		pq.pop();
		if(d != dist[ind][x][y]) continue;
		
		populate_edge_list(ind, x, y, edge_list);
		for(auto& tmp:edge_list){
			int ni, nx, ny; tie(ni, nx, ny) = tmp.first;
			ll nd=tmp.second;
			if(dist[ni][nx][ny] > d+nd){
				dist[ni][nx][ny] = d+nd;
				pq.emplace(-dist[ni][nx][ny], t3{ni, nx, ny});
			}
		}
	}
	printf("%lld\n", dist[0][tx][ty]);
}

int main()
{
    in();
    find_nearest();
    dijk();
    return 0;
}

Compilation message

soccer.cpp: In function 'void read(int&)':
soccer.cpp:5:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 28132 KB Output is correct
2 Correct 12 ms 20736 KB Output is correct
3 Correct 860 ms 47688 KB Output is correct
4 Correct 937 ms 47432 KB Output is correct
5 Correct 144 ms 22392 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1043 ms 47432 KB Output is correct
2 Correct 1016 ms 47432 KB Output is correct
3 Correct 766 ms 47048 KB Output is correct
4 Correct 660 ms 47432 KB Output is correct
5 Correct 756 ms 47432 KB Output is correct
6 Correct 767 ms 47436 KB Output is correct
7 Correct 938 ms 47432 KB Output is correct
8 Correct 876 ms 47432 KB Output is correct
9 Correct 952 ms 47432 KB Output is correct
10 Correct 140 ms 29024 KB Output is correct
11 Correct 933 ms 47564 KB Output is correct
12 Correct 1004 ms 47432 KB Output is correct
13 Correct 561 ms 47120 KB Output is correct
14 Correct 948 ms 47432 KB Output is correct
15 Correct 755 ms 47436 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 28132 KB Output is correct
2 Correct 12 ms 20736 KB Output is correct
3 Correct 860 ms 47688 KB Output is correct
4 Correct 937 ms 47432 KB Output is correct
5 Correct 144 ms 22392 KB Output is correct
6 Correct 1043 ms 47432 KB Output is correct
7 Correct 1016 ms 47432 KB Output is correct
8 Correct 766 ms 47048 KB Output is correct
9 Correct 660 ms 47432 KB Output is correct
10 Correct 756 ms 47432 KB Output is correct
11 Correct 767 ms 47436 KB Output is correct
12 Correct 938 ms 47432 KB Output is correct
13 Correct 876 ms 47432 KB Output is correct
14 Correct 952 ms 47432 KB Output is correct
15 Correct 140 ms 29024 KB Output is correct
16 Correct 933 ms 47564 KB Output is correct
17 Correct 1004 ms 47432 KB Output is correct
18 Correct 561 ms 47120 KB Output is correct
19 Correct 948 ms 47432 KB Output is correct
20 Correct 755 ms 47436 KB Output is correct
21 Correct 159 ms 22464 KB Output is correct
22 Correct 1236 ms 47564 KB Output is correct
23 Correct 1183 ms 34904 KB Output is correct
24 Correct 1362 ms 35160 KB Output is correct
25 Correct 1109 ms 47564 KB Output is correct
26 Correct 1063 ms 47512 KB Output is correct
27 Correct 498 ms 23752 KB Output is correct
28 Correct 560 ms 23800 KB Output is correct
29 Correct 938 ms 35904 KB Output is correct
30 Correct 600 ms 25068 KB Output is correct
31 Correct 1037 ms 47688 KB Output is correct
32 Correct 1285 ms 48200 KB Output is correct
33 Correct 819 ms 47432 KB Output is correct
34 Correct 1296 ms 47488 KB Output is correct
35 Correct 399 ms 23796 KB Output is correct