Submission #544207

#	Time	Username	Problem	Language	Result	Execution time	Memory
544207		Antekb	Soccer (JOI17_soccer)	C++14	100 / 100	1008 ms	66804 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[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 (stderr)

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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65