oj.uz

Submission #544207

# Submission time Handle Problem Language Result Execution time Memory
544207 2022-04-01T10:32:13 Z Antekb Soccer (JOI17_soccer) C++14
100 / 100
 1008 ms 66804 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[6][N][N];
    int dist[N][N], vis[6][N][N];//edg, 4-brak, 5-ktos
    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++){
    			for(int k=0; k<6; k++)d[k][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[4][x][y]=d[5][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]--;
    			for(int k=0; k<6; k++)Q.emplace(make_pair(-d[k][i][j], k), 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;
            //cout<<t<<" "<<x<<" "<<y<<" "<<d[t][x][y]<<"\n";
    		if(t!=4 && d[4][x][y]>d[t][x][y]){
    			d[4][x][y]=d[t][x][y];
    			Q.emplace(make_pair(-d[4][x][y], 4), make_pair(x, y));
    		}
    		if(t==4 && d[5][x][y]>d[4][x][y]+dist[x][y]*1ll*c){
    			d[5][x][y]=d[4][x][y]+dist[x][y]*1ll*c;
    			Q.emplace(make_pair(-d[5][x][y], 5), make_pair(x, y));			
    		}
            if(t==5){
    		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));
    			}
    		}
            }
            else if(t!=4){
                auto e=edg[t];
                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]+a){
                    d[t][x+e.st][y+e.nd]=d[t][x][y]+a;
                    Q.emplace(make_pair(-d[t][x+e.st][y+e.nd], t), make_pair(x+e.st, y+e.nd));
                }
            }
    		if(t==5){
    			/*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 tt=0; tt<4; tt++){
                    if(d[t][x][y]+b<d[tt][x][y]){
                        d[tt][x][y]=d[t][x][y]+b;
                        Q.emplace(make_pair(-d[tt][x][y], tt), make_pair(x, y));
                    }
                }
    		}
            /*if(Q.size()>3e6){
                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[4][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 183 ms 22092 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 729 ms 65876 KB Output is correct
4 Correct 734 ms 65984 KB Output is correct
5 Correct 237 ms 35376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 65868 KB Output is correct
2 Correct 821 ms 65868 KB Output is correct
3 Correct 629 ms 62972 KB Output is correct
4 Correct 708 ms 65964 KB Output is correct
5 Correct 632 ms 65536 KB Output is correct
6 Correct 740 ms 65964 KB Output is correct
7 Correct 774 ms 65992 KB Output is correct
8 Correct 760 ms 65952 KB Output is correct
9 Correct 803 ms 65940 KB Output is correct
10 Correct 131 ms 30400 KB Output is correct
11 Correct 789 ms 65904 KB Output is correct
12 Correct 828 ms 65976 KB Output is correct
13 Correct 559 ms 62952 KB Output is correct
14 Correct 786 ms 65884 KB Output is correct
15 Correct 629 ms 65564 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 22092 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 729 ms 65876 KB Output is correct
4 Correct 734 ms 65984 KB Output is correct
5 Correct 237 ms 35376 KB Output is correct
6 Correct 851 ms 65868 KB Output is correct
7 Correct 821 ms 65868 KB Output is correct
8 Correct 629 ms 62972 KB Output is correct
9 Correct 708 ms 65964 KB Output is correct
10 Correct 632 ms 65536 KB Output is correct
11 Correct 740 ms 65964 KB Output is correct
12 Correct 774 ms 65992 KB Output is correct
13 Correct 760 ms 65952 KB Output is correct
14 Correct 803 ms 65940 KB Output is correct
15 Correct 131 ms 30400 KB Output is correct
16 Correct 789 ms 65904 KB Output is correct
17 Correct 828 ms 65976 KB Output is correct
18 Correct 559 ms 62952 KB Output is correct
19 Correct 786 ms 65884 KB Output is correct
20 Correct 629 ms 65564 KB Output is correct
21 Correct 251 ms 34096 KB Output is correct
22 Correct 942 ms 65868 KB Output is correct
23 Correct 863 ms 64468 KB Output is correct
24 Correct 1008 ms 65904 KB Output is correct
25 Correct 852 ms 65960 KB Output is correct
26 Correct 900 ms 65916 KB Output is correct
27 Correct 765 ms 66388 KB Output is correct
28 Correct 793 ms 66724 KB Output is correct
29 Correct 868 ms 66600 KB Output is correct
30 Correct 737 ms 66804 KB Output is correct
31 Correct 844 ms 65920 KB Output is correct
32 Correct 970 ms 66640 KB Output is correct
33 Correct 766 ms 66040 KB Output is correct
34 Correct 983 ms 65948 KB Output is correct
35 Correct 705 ms 66672 KB Output is correct