oj.uz

Submission #544191

# Submission time Handle Problem Language Result Execution time Memory
544191 2022-04-01T09:51:43 Z Antekb Soccer (JOI17_soccer) C++14
35 / 100
 3000 ms 40748 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);
			}
		}
	}
	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

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 177 ms 12488 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1018 ms 40652 KB Output is correct
4 Correct 981 ms 40652 KB Output is correct
5 Correct 288 ms 17344 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1216 ms 40624 KB Output is correct
2 Correct 1221 ms 40652 KB Output is correct
3 Correct 779 ms 32508 KB Output is correct
4 Correct 982 ms 40668 KB Output is correct
5 Correct 804 ms 34104 KB Output is correct
6 Correct 1035 ms 40656 KB Output is correct
7 Correct 1207 ms 40580 KB Output is correct
8 Correct 1043 ms 40672 KB Output is correct
9 Correct 1160 ms 40660 KB Output is correct
10 Correct 117 ms 12636 KB Output is correct
11 Correct 1184 ms 40548 KB Output is correct
12 Correct 1140 ms 40740 KB Output is correct
13 Correct 771 ms 32520 KB Output is correct
14 Correct 1208 ms 40748 KB Output is correct
15 Correct 897 ms 34104 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 12488 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1018 ms 40652 KB Output is correct
4 Correct 981 ms 40652 KB Output is correct
5 Correct 288 ms 17344 KB Output is correct
6 Correct 1216 ms 40624 KB Output is correct
7 Correct 1221 ms 40652 KB Output is correct
8 Correct 779 ms 32508 KB Output is correct
9 Correct 982 ms 40668 KB Output is correct
10 Correct 804 ms 34104 KB Output is correct
11 Correct 1035 ms 40656 KB Output is correct
12 Correct 1207 ms 40580 KB Output is correct
13 Correct 1043 ms 40672 KB Output is correct
14 Correct 1160 ms 40660 KB Output is correct
15 Correct 117 ms 12636 KB Output is correct
16 Correct 1184 ms 40548 KB Output is correct
17 Correct 1140 ms 40740 KB Output is correct
18 Correct 771 ms 32520 KB Output is correct
19 Correct 1208 ms 40748 KB Output is correct
20 Correct 897 ms 34104 KB Output is correct
21 Execution timed out 3062 ms 16236 KB Time limit exceeded
22 Halted 0 ms 0 KB -