oj.uz

Submission #535467

# Submission time Handle Problem Language Result Execution time Memory
535467 2022-03-10T10:12:06 Z amunduzbaev Soccer (JOI17_soccer) C++17
100 / 100
 2079 ms 11680 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int M = 1e5 + 5;
const int N = 505;
int _d[N][N], used[N][N];
int d[N][N][2], x[M], y[M];
int mn[N], p[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m; n++, m++;
	int a, b, c; cin>>a>>b>>c;
	int k; cin>>k;
	memset(d, 63, sizeof d);
	queue<int> q;
	
	for(int i=0;i<k;i++){
		cin>>x[i]>>y[i];
		if(i+1 < k){
			used[x[i]][y[i]] = 1;
			q.push(x[i] * m + y[i]);
		}
	}
	
	int ch[4][2] = {
		{0, 1},
		{0, -1},
		{1, 0},
		{-1, 0}
	};
	auto check = [&](int x, int y){ return (0 <= x && x < n && 0 <= y && y < m); };
	while(!q.empty()){
		int u = q.front(); q.pop();
		int i = u/m, j = u%m;
		for(int t=0;t<4;t++){
			int x = i + ch[t][0], y = j + ch[t][1];
			if(check(x, y) && !used[x][y]){
				_d[x][y] = _d[i][j] + 1;
				used[x][y] = 1;
				q.push(x * m + y);
			}
		}
	}
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout<<_d[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
		
	memset(used, 0, sizeof used);
	memset(mn, 63, sizeof mn);
	memset(p, -1, sizeof p);
	int i = x[0], j = y[0];
	used[i][j] = 1;
	d[i][j][1] = d[i][j][0] = 0;
	
	auto print = [&](){
		for(int t=0;t<2;t++){
			for(int i=0;i<n;i++){
				for(int j=0;j<m;j++){
					cout<<d[i][j][t]<<" ";
				} cout<<"\n";
			} cout<<"\n";
		}
	};
	
	while(~j){
		//~ for(int i=0;i<=n;i++) cout<<mn[i]<<" "<<p[i]<<"\n";
		//~ cout<<"\n";
		auto upd = [&](int i, int j){
			if(mn[i] > d[i][j][1]){
				mn[i] = d[i][j][1];
				p[i] = j;
			}
		};
		
		for(int l=0;l<m;l++){
			int D = d[i][j][1] + abs(l - j) * a + b;
			d[i][l][0] = min(d[i][l][0], D);
			
			if(d[i][l][1] > D + _d[i][l] * c){
				d[i][l][1] = D + _d[i][l] * c;
				upd(i, l);
			}
		} for(int l=0;l<n;l++){
			int D = d[i][j][1] + abs(i - l) * a + b;
			d[l][j][0] = min(d[l][j][0], D);
			
			if(d[l][j][1] > D + _d[l][j] * c){
				d[l][j][1] = D + _d[l][j] * c;
				upd(l, j);
			}
		}
		for(int t=0;t<4;t++){
			int x = i + ch[t][0], y = j + ch[t][1];
			if(!check(x, y)) continue;
			d[x][y][0] = min(d[x][y][0], d[i][j][1] + c);
			if(d[x][y][1] > d[i][j][1] + c){
				d[x][y][1] = d[i][j][1] + c;
				upd(x, y);
			}
		}
		
		i = 0, j = p[0];
		for(int l=0;l<n;l++){
			if(mn[l] < mn[i]){
				i = l;
				j = p[i];
			}
		}

		//~ cout<<i<<" "<<j<<"\n";
		//~ for(int i=0;i<=n;i++) cout<<mn[i]<<" "<<p[i]<<"\n";
		//~ cout<<"\n";
		
		if(~j) used[i][j] = 1;
		
		mn[i] = 1e18, p[i] = -1;
		for(int l=0;l<m;l++){
			if(used[i][l]) continue;
			upd(i, l);
		}
		
		//~ print();
	}
	
	cout<<d[x[k-1]][y[k-1]][0]<<"\n";
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:63:7: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   63 |  auto print = [&](){
      |       ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 7512 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 1315 ms 8300 KB Output is correct
4 Correct 1113 ms 8300 KB Output is correct
5 Correct 222 ms 7636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 8332 KB Output is correct
2 Correct 1428 ms 8344 KB Output is correct
3 Correct 792 ms 7928 KB Output is correct
4 Correct 1255 ms 8300 KB Output is correct
5 Correct 894 ms 8352 KB Output is correct
6 Correct 1526 ms 8336 KB Output is correct
7 Correct 1674 ms 8480 KB Output is correct
8 Correct 1370 ms 8404 KB Output is correct
9 Correct 1642 ms 8484 KB Output is correct
10 Correct 122 ms 8380 KB Output is correct
11 Correct 1647 ms 8472 KB Output is correct
12 Correct 1558 ms 8356 KB Output is correct
13 Correct 677 ms 7892 KB Output is correct
14 Correct 1577 ms 8468 KB Output is correct
15 Correct 1199 ms 8448 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 7512 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 1315 ms 8300 KB Output is correct
4 Correct 1113 ms 8300 KB Output is correct
5 Correct 222 ms 7636 KB Output is correct
6 Correct 1378 ms 8332 KB Output is correct
7 Correct 1428 ms 8344 KB Output is correct
8 Correct 792 ms 7928 KB Output is correct
9 Correct 1255 ms 8300 KB Output is correct
10 Correct 894 ms 8352 KB Output is correct
11 Correct 1526 ms 8336 KB Output is correct
12 Correct 1674 ms 8480 KB Output is correct
13 Correct 1370 ms 8404 KB Output is correct
14 Correct 1642 ms 8484 KB Output is correct
15 Correct 122 ms 8380 KB Output is correct
16 Correct 1647 ms 8472 KB Output is correct
17 Correct 1558 ms 8356 KB Output is correct
18 Correct 677 ms 7892 KB Output is correct
19 Correct 1577 ms 8468 KB Output is correct
20 Correct 1199 ms 8448 KB Output is correct
21 Correct 305 ms 7528 KB Output is correct
22 Correct 1369 ms 8344 KB Output is correct
23 Correct 1133 ms 8180 KB Output is correct
24 Correct 1524 ms 8532 KB Output is correct
25 Correct 2079 ms 8396 KB Output is correct
26 Correct 1420 ms 8688 KB Output is correct
27 Correct 1399 ms 10852 KB Output is correct
28 Correct 1547 ms 11680 KB Output is correct
29 Correct 1547 ms 11468 KB Output is correct
30 Correct 1438 ms 11488 KB Output is correct
31 Correct 1544 ms 8484 KB Output is correct
32 Correct 1701 ms 11480 KB Output is correct
33 Correct 1427 ms 8332 KB Output is correct
34 Correct 1836 ms 8524 KB Output is correct
35 Correct 1416 ms 11596 KB Output is correct