oj.uz

Submission #544203

# Submission time Handle Problem Language Result Execution time Memory
544203 2022-04-01T10:17:53 Z Antekb Soccer (JOI17_soccer) C++14
35 / 100
 3000 ms 54328 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));
    				}
    			}
    		}
            if(Q.size()>2e6){
                while(Q.size()){
                    Q.pop();
                }
                for(int i=1; i<=h; i++){
                    for(int j=1; j<=w; j++){
                        if(!vis[0][i][j])Q.emplace(make_pair(-d[0][i][j], 0), make_pair(i, j));
                        if(!vis[1][i][j])Q.emplace(make_pair(-d[1][i][j], 1), make_pair(i, 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:20: 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:21: warning: unused variable 'sx' [-Wunused-variable]
   23 |      int n, tx, ty, sx, sy;
      |                     ^~
soccer.cpp:23:25: 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 119 ms 10816 KB Output is correct
2 Correct 2 ms 788 KB Output is correct
3 Correct 703 ms 34408 KB Output is correct
4 Correct 692 ms 34340 KB Output is correct
5 Correct 207 ms 12452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 34340 KB Output is correct
2 Correct 793 ms 34344 KB Output is correct
3 Correct 577 ms 33088 KB Output is correct
4 Correct 688 ms 34456 KB Output is correct
5 Correct 578 ms 34328 KB Output is correct
6 Correct 728 ms 34388 KB Output is correct
7 Correct 848 ms 34344 KB Output is correct
8 Correct 777 ms 34340 KB Output is correct
9 Correct 780 ms 34356 KB Output is correct
10 Correct 87 ms 10772 KB Output is correct
11 Correct 814 ms 34348 KB Output is correct
12 Correct 781 ms 34396 KB Output is correct
13 Correct 504 ms 33020 KB Output is correct
14 Correct 845 ms 34344 KB Output is correct
15 Correct 621 ms 34396 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 10816 KB Output is correct
2 Correct 2 ms 788 KB Output is correct
3 Correct 703 ms 34408 KB Output is correct
4 Correct 692 ms 34340 KB Output is correct
5 Correct 207 ms 12452 KB Output is correct
6 Correct 785 ms 34340 KB Output is correct
7 Correct 793 ms 34344 KB Output is correct
8 Correct 577 ms 33088 KB Output is correct
9 Correct 688 ms 34456 KB Output is correct
10 Correct 578 ms 34328 KB Output is correct
11 Correct 728 ms 34388 KB Output is correct
12 Correct 848 ms 34344 KB Output is correct
13 Correct 777 ms 34340 KB Output is correct
14 Correct 780 ms 34356 KB Output is correct
15 Correct 87 ms 10772 KB Output is correct
16 Correct 814 ms 34348 KB Output is correct
17 Correct 781 ms 34396 KB Output is correct
18 Correct 504 ms 33020 KB Output is correct
19 Correct 845 ms 34344 KB Output is correct
20 Correct 621 ms 34396 KB Output is correct
21 Execution timed out 3067 ms 54328 KB Time limit exceeded
22 Halted 0 ms 0 KB -