Submission #1180375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180375		pythontest	Soccer (JOI17_soccer)	C++20	100 / 100	762 ms	142576 KiB

soccer

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
constexpr int H=507;
constexpr int L=3;
vector<pair<long long,long long>> graf[L*H*H];
vector<int> graf2[H*H];
long long dist[L*H*H];
int dist2[H*H];
int main() {
    long long h,w,a,b,c,n;
    scanf("%lld %lld %lld %lld %lld %lld",&h,&w,&a,&b,&c,&n);
    vector<pair<int,int>> pilkarzyki;
    for(int i=0;i<n-1;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        pilkarzyki.push_back({x,y});
    }
    int sx,sy;
    scanf("%d %d",&sx,&sy);
    for(int i=0;i<=h;i++){
        for(int j=0;j<=w;j++){
            int nn=i*H+j;
            if(i>0) {
                graf2[nn].push_back((i-1)*H+j);
                graf[nn].push_back({(i-1)*H+j,c});
                graf[H*H+nn].push_back({H*H+(i-1)*H+j,a});
            }
            if(j>0) {
                graf2[nn].push_back(nn-1);
                graf[nn].push_back({nn-1,c});
                graf[2*H*H+nn].push_back({2*H*H+nn-1,a});
            }
            graf2[nn].push_back(nn+1);
            graf[nn].push_back({nn+1,c});
            graf[2*H*H+nn].push_back({2*H*H+nn+1,a});
            graf2[nn].push_back((i+1)*H+j);
            graf[nn].push_back({(i+1)*H+j,c});
            graf[H*H+nn].push_back({H*H+(i+1)*H+j,a});
            dist2[nn]=1e8;
            dist[nn]=dist[H*H+nn]=dist[2*H*H+nn]=1e17;
        }
    }
    queue<int> kolejka;
    for(auto x:pilkarzyki){
        kolejka.push(x.first*H+x.second);
        dist2[x.first*H+x.second]=0;
    }
    dist2[sx*H+sy]=0;
    while(!kolejka.empty()){
        auto top = kolejka.front();
        kolejka.pop();
        for(auto x:graf2[top]){
            if(dist2[x]>dist2[top]+1){
                dist2[x]=dist2[top]+1;
                kolejka.push(x);
            }
        }
    }
    for(int i=0;i<=h;i++){
        for(int j=0;j<=w;j++){
            graf[H*H+i*H+j].push_back({i*H+j,b+dist2[i*H+j]*c});
            graf[i*H+j].push_back({H*H+i*H+j,0});
            graf[2*H*H+i*H+j].push_back({i*H+j,b+dist2[i*H+j]*c});
            graf[i*H+j].push_back({2*H*H+i*H+j,0});
        }
    }
    priority_queue<pair<long long, int>> pq;
    pq.push({0,H*pilkarzyki[0].first+pilkarzyki[0].second});
    dist[H*pilkarzyki[0].first+pilkarzyki[0].second]=0;
    while(!pq.empty()){
        auto top = pq.top();
        pq.pop();
        if(dist[top.second]<-top.first) continue;
        for(auto x:graf[top.second]){
            if(dist[x.first]>x.second-top.first){
                dist[x.first]=x.second-top.first;
                pq.push({-dist[x.first],x.first});
            }
        }
    }
    printf("%lld",dist[sx*H+sy]);
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%lld %lld %lld %lld %lld %lld",&h,&w,&a,&b,&c,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
soccer.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %d",&sx,&sy);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65