제출 #1180291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180291		user736482	Soccer (JOI17_soccer)	C++20	100 / 100	1014 ms	125636 KiB

soccer

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define MX 507

ll n,q,s,t,a,b,c,d,ans,k,e,m,pier,h,w;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
bool odw[1000007];
ll dst[1000007];
vector<pair<ll,ll>>g[1000000];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>h>>w>>a>>b>>c>>n;
    h++;
    w++;
    for(ll i=0;i<n-1;i++){
        cin>>d>>e;
       // d--;
      //  e--;
        if(!i)pier=d*MX+e;
        pq.push({0,d*MX+e});
    }
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
            if(i)
                g[i*MX+j].pb({c,i*MX-MX+j});
            if(j)
                g[i*MX+j].pb({c,i*MX+j-1});
            if(i+1<h)
                g[i*MX+j].pb({c,i*MX+MX+j});
            if(j+1<w)
                g[i*MX+j].pb({c,i*MX+1+j});
            if(i)
                g[i*MX+j+MX*MX].pb({a,i*MX-MX+j+MX*MX});
            if(j)
                g[i*MX+j+MX*MX*2].pb({a,i*MX-1+j+MX*MX*2});
            if(i+1<h)
                g[i*MX+j+MX*MX].pb({a,i*MX+MX+j+MX*MX});
            if(j+1<w)
                g[i*MX+j+MX*MX*2].pb({a,i*MX+1+j+MX*MX*2});
        }
    }
    
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
           // for(pair<ll,ll> k : g[i*MX+j])cout<<k.ss/MX<<" "<<k.ss%MX<<"  ";
          //  cout<<"\n";
        }
    }
   // return 0;
    while(pq.size()){
        auto pom=pq.top();
       // cout<<pom.ff<<" "<<pom.ss<<"\n"<<flush;
        pq.pop();
        if(!odw[pom.ss]){
            odw[pom.ss]=1;
            dst[pom.ss]=pom.ff;
            for(pair<ll,ll> i : g[pom.ss])
                pq.push({i.ff+pom.ff,i.ss});
        }
    }//return 0;
    cin>>d>>e;
    d=d*MX+e;
    dst[d]=0;
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
            g[i*MX+j].pb({b,i*MX+j+MX*MX});
            g[i*MX+j].pb({b,i*MX+j+2*MX*MX});
            g[i*MX+j+2*MX*MX].pb({dst[i*MX+j],i*MX+j});
            g[i*MX+j+MX*MX].pb({dst[i*MX+j],i*MX+j});
        }
    }
    pq.push({0,pier});
    for(ll i=0;i<507;i++){
        for(ll j=0;j<MX;j++)odw[i*MX+j]=0;
    }
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
      //      for(pair<ll,ll> k : g[i*MX+j])cout<<k.ss/MX<<" "<<k.ss%MX<<"  ";
      //      cout<<"\n";
        }
    }
   // cout<<"\n\n";
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
            //for(pair<ll,ll> k : g[i*MX+j+MX*MX])cout<<k.ss/MX<<" "<<k.ss%MX<<"  ";
           // cout<<"\n";
        }
    }
   // return 0;
    //return 0;
    ll cnt=0;
    while(pq.size()){
        cnt++;
        auto pom=pq.top();
        pq.pop();
        
        
       // cout<<pom.ss<<" "<<pom.ss/MX<<" "<<pom.ss%MX<<"\n"<<flush;
        if(!odw[pom.ss]){
            
            //cout<<pom.ff<<" "<<pom.ss/MX/MX<<" "<<(pom.ss/MX)%MX<<" "<<pom.ss%MX<<"\n"<<flush;
          //  cout<<pom.ff<<" "<<pom.ss<<"\n"<<flush;
            odw[pom.ss]=1;

            dst[pom.ss]=pom.ff;
            
            for(pair<ll,ll> i : g[pom.ss])
                pq.push({i.ff+pom.ff,i.ss});
        }
    }
    //cout<<dst[0]<<flush;
    //cout<<"xd"<<flush;
    //return 0;
    
   // cout<<d<<flush;
    cout<<dst[d];
}

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