oj.uz

Submission #544182

# Submission time Handle Problem Language Result Execution time Memory
544182 2022-04-01T09:44:14 Z Antekb Soccer (JOI17_soccer) C++14
35 / 100
 878 ms 262144 KB 
#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);
			}
		}
	}
	priority_queue<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.emplace(make_pair(-d[0][i][j], 0), make_pair(i, j));
			Q.emplace(make_pair(-d[1][i][j], 1), make_pair(i, j));
		}
	}
	while(Q.size()){
		int t=Q.top().st.nd, x=Q.top().nd.st, y=Q.top().nd.nd;
		Q.pop();
		if(vis[t][x][y])continue;
		vis[t][x][y]=1;
		if(t==1 && d[0][x][y]>d[1][x][y]){
			d[0][x][y]=d[t][x][y];
			Q.emplace(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){
			d[1][x][y]=d[0][x][y]+dist[x][y]*1ll*c;
			Q.emplace(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){
				d[t][x+e.st][y+e.nd]=d[t][x][y]+c;
				Q.emplace(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)){
					d[0][i][y]=d[1][x][y]+b+ll(a)*abs(i-x);
					Q.emplace(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)){
					d[0][x][j]=d[1][x][y]+b+ll(a)*abs(j-y);
					Q.emplace(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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10816 KB Output is correct
2 Correct 3 ms 788 KB Output is correct
3 Correct 723 ms 34412 KB Output is correct
4 Correct 719 ms 34344 KB Output is correct
5 Correct 209 ms 12480 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 34408 KB Output is correct
2 Correct 822 ms 34548 KB Output is correct
3 Correct 568 ms 33212 KB Output is correct
4 Correct 673 ms 34512 KB Output is correct
5 Correct 590 ms 34336 KB Output is correct
6 Correct 747 ms 34460 KB Output is correct
7 Correct 855 ms 34684 KB Output is correct
8 Correct 829 ms 34472 KB Output is correct
9 Correct 803 ms 34476 KB Output is correct
10 Correct 87 ms 10668 KB Output is correct
11 Correct 878 ms 34460 KB Output is correct
12 Correct 806 ms 34460 KB Output is correct
13 Correct 515 ms 33132 KB Output is correct
14 Correct 863 ms 34432 KB Output is correct
15 Correct 635 ms 34396 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10816 KB Output is correct
2 Correct 3 ms 788 KB Output is correct
3 Correct 723 ms 34412 KB Output is correct
4 Correct 719 ms 34344 KB Output is correct
5 Correct 209 ms 12480 KB Output is correct
6 Correct 832 ms 34408 KB Output is correct
7 Correct 822 ms 34548 KB Output is correct
8 Correct 568 ms 33212 KB Output is correct
9 Correct 673 ms 34512 KB Output is correct
10 Correct 590 ms 34336 KB Output is correct
11 Correct 747 ms 34460 KB Output is correct
12 Correct 855 ms 34684 KB Output is correct
13 Correct 829 ms 34472 KB Output is correct
14 Correct 803 ms 34476 KB Output is correct
15 Correct 87 ms 10668 KB Output is correct
16 Correct 878 ms 34460 KB Output is correct
17 Correct 806 ms 34460 KB Output is correct
18 Correct 515 ms 33132 KB Output is correct
19 Correct 863 ms 34432 KB Output is correct
20 Correct 635 ms 34396 KB Output is correct
21 Runtime error 541 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -