Submission #1277652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277652		trandangquang	Soccer (JOI17_soccer)	C++20	100 / 100	251 ms	19032 KiB

soccer

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int H=505;
const int N=1e5+5;

int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};

int h,w,a,b,c,n;
int s[N],t[N];
int minP[H][H]; ll d[H][H][5];

bool inBoard(int x, int y){
    return x>=0 && y>=0 && x<=h && y<=w;
}

void bfs(){
    memset(minP,0x3f,sizeof(minP));

    queue<ii> q;
    foru(i,1,n){
        minP[s[i]][t[i]]=0;
        q.push(ii(s[i],t[i]));
    }

    while(q.size()){
        auto [ux,uy]=q.front(); q.pop();

        rep(i,4){
            int vx=ux+dx[i], vy=uy+dy[i];
            if(!inBoard(vx,vy)) continue;

            if(minP[vx][vy]>minP[ux][uy]+1){
                minP[vx][vy]=minP[ux][uy]+1;
                q.push(ii(vx,vy));
            }
        }
    }

//    cout << minP[1][4] <<'\n';
}

void dijkstra(){
    memset(d,0x3f,sizeof(d));
    d[s[1]][t[1]][4]=0;

    struct Node{
        int ux,uy,ud; ll d;
        bool operator < (const Node &o) const {
            return d > o.d;
        }
    };

    priority_queue<Node> pq;
    pq.push({s[1],t[1],4,0});

    while(pq.size()){
        Node tp=pq.top(); pq.pop();
        if(tp.d > d[tp.ux][tp.uy][tp.ud]) continue;

        if(tp.ud==4){
            rep(i,4){
                int vx=tp.ux+dx[i], vy=tp.uy+dy[i], vd=tp.ud;
                if(!inBoard(vx,vy)) continue;

                if(d[vx][vy][vd] > tp.d + c){
                    d[vx][vy][vd] = tp.d + c;
                    pq.push({vx, vy, vd, d[vx][vy][vd]});
                }
            }
            rep(i,4){
                if(d[tp.ux][tp.uy][i] > tp.d + b){
                    d[tp.ux][tp.uy][i] = tp.d + b;
                    pq.push({tp.ux, tp.uy, i, tp.d+b});
                }
            }
        } else{
            int vx=tp.ux+dx[tp.ud], vy=tp.uy+dy[tp.ud], vd=tp.ud;
            if(inBoard(vx,vy)){
                if(d[vx][vy][vd] > tp.d + a){
                    d[vx][vy][vd] = tp.d + a;
                    pq.push({vx, vy, vd, d[vx][vy][vd]});
                }
            }

            if(d[tp.ux][tp.uy][4] > tp.d + 1LL * minP[tp.ux][tp.uy] * c){
                d[tp.ux][tp.uy][4] = tp.d + 1LL * minP[tp.ux][tp.uy] * c;
                pq.push({tp.ux, tp.uy, 4, d[tp.ux][tp.uy][4]});
            }
        }
    }

    ll res=1e18;
    rep(i,5) mini(res, d[s[n]][t[n]][i]);
    cout<<res<<'\n';
}

void solve(){
    cin>>h>>w;
    cin>>a>>b>>c;
    cin>>n;
    foru(i,1,n) cin>>s[i]>>t[i];

    bfs();
    dijkstra();
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; // cin>>tc;
    rep(i,tc){
        solve();
    }
}

Compilation message (stderr)

soccer.cpp: In function 'int32_t main()':
soccer.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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