Submission #544191

#	Time	Username	Problem	Language	Result	Execution time	Memory
544191		Antekb	Soccer (JOI17_soccer)	C++14	35 / 100	3062 ms	40748 KiB

soccer

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=505;
using ll = long long;
const ll INF=1e18;
ll d[2][N][N];
int dist[N][N], vis[2][N][N];
vector<pair<int, int> > edg={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main(){
	int h, w, a, b, c;
	cin>>h>>w>>a>>b>>c;
	h++;
	w++;
	for(int i=1; i<=h; i++){
		dist[i][0]=dist[i][w+1]=1;
		for(int j=1; j<=w; j++){
			d[0][i][j]=d[1][i][j]=INF;
			dist[0][j]=dist[h+1][j]=1;
		}
	}
	int n, tx, ty, sx, sy;
	cin>>n;
	vector<pair<int, int> > V;
	for(int i=1; i<n; i++){
		int x, y;
		cin>>x>>y;
		x++;
		y++;
		if(i==1){
			d[0][x][y]=d[1][x][y]=0;
		}
		if(!dist[x][y]){
			dist[x][y]=1;
			V.emplace_back(x, y);
		}
	}
	cin>>tx>>ty;
	tx++;
	ty++;
	for(int i=0; i<V.size(); i++){
		int x=V[i].st, y=V[i].nd;
		//cout<<x<<" "<<y<<endl;
		//assert(x&&y);
		for(auto e:edg){
			if(!dist[x+e.st][y+e.nd]){
				dist[x+e.st][y+e.nd]=dist[x][y]+1;
				V.emplace_back(x+e.st, y+e.nd);
			}
		}
	}
	set<pair<pair<ll, int>, pair<int, int> > > Q;
	for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
			dist[i][j]--;
			Q.insert({make_pair(d[0][i][j], 0), make_pair(i, j)});
			Q.insert({make_pair(d[1][i][j], 1), make_pair(i, j)});
		}
	}
	while(Q.size()){
		int t=(*Q.begin()).st.nd, x=(*Q.begin()).nd.st, y=(*Q.begin()).nd.nd;
		Q.erase(Q.begin());
		if(vis[t][x][y])continue;
		vis[t][x][y]=1;
		if(t==1 && d[0][x][y]>d[1][x][y]){
			Q.erase(Q.find({make_pair(d[0][x][y], 0), make_pair(x, y)}));
			d[0][x][y]=d[t][x][y];
			Q.insert({make_pair(d[0][x][y], 0), make_pair(x, y)});
		}
		if(t==0 && d[1][x][y]>d[0][x][y]+dist[x][y]*1ll*c){
			Q.erase(Q.find({make_pair(d[1][x][y], 1), make_pair(x, y)}));			
			d[1][x][y]=d[0][x][y]+dist[x][y]*1ll*c;
			Q.insert({make_pair(d[1][x][y], 1), make_pair(x, y)});			
		}
		for(auto e:edg){
			if((x+e.st && y+e.nd && x+e.st-h-1 && y+e.nd-w-1) && d[t][x+e.st][y+e.nd]>d[t][x][y]+c){
				Q.erase(Q.find({make_pair(d[t][x+e.st][y+e.nd], t), make_pair(x+e.st, y+e.nd)}));
				d[t][x+e.st][y+e.nd]=d[t][x][y]+c;
				Q.insert({make_pair(d[t][x+e.st][y+e.nd], t), make_pair(x+e.st, y+e.nd)});
			}
		}
		if(t==1){
			for(int i=1; i<=h; i++){
				if(d[0][i][y]>d[1][x][y]+b+ll(a)*abs(i-x)){
					Q.erase(Q.find({make_pair(d[0][i][y], 0), make_pair(i, y)}));
					d[0][i][y]=d[1][x][y]+b+ll(a)*abs(i-x);
					Q.insert({make_pair(d[0][i][y], 0), make_pair(i, y)});
				}
			}
			for(int j=1; j<=w; j++){
				if(d[0][x][j]>d[1][x][y]+b+ll(a)*abs(j-y)){
					Q.erase(Q.find({make_pair(d[0][x][j], 0), make_pair(x, j)}));
					d[0][x][j]=d[1][x][y]+b+ll(a)*abs(j-y);
					Q.insert({make_pair(d[0][x][j], 0), make_pair(x, j)});
				}
			}
		}
	}
	/*for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
			cout<<d[0][i][j]<<" \n"[j==w];
		}
	}
	cout<<"\n";
	for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
			cout<<d[1][i][j]<<" \n"[j==w];
		}
	}*/
	cout<<d[0][tx][ty];
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
soccer.cpp:23:17: warning: unused variable 'sx' [-Wunused-variable]
   23 |  int n, tx, ty, sx, sy;
      |                 ^~
soccer.cpp:23:21: warning: unused variable 'sy' [-Wunused-variable]
   23 |  int n, tx, ty, sx, sy;
      |                     ^~

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