Submission #535467

#	Time	Username	Problem	Language	Result	Execution time	Memory
535467		amunduzbaev	Soccer (JOI17_soccer)	C++17	100 / 100	2079 ms	11680 KiB

soccer

#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 (stderr)

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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65