Submission #544203

#	Time	Username	Problem	Language	Result	Execution time	Memory
544203		Antekb	Soccer (JOI17_soccer)	C++14	35 / 100	3067 ms	54328 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[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 (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: 0 / 65