Submission #1180292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180292		Szymon_Pilipczuk	Soccer (JOI17_soccer)	C++20	100 / 100	730 ms	30304 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define rep(a,b) for(int a = 0;a<b;a++)
#define ll long long
vector<vector<ll>> dis;
priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> pq;
ll cs[501][501][5];
ll a,b,c;
ll h,w;
ll infl = 1e18;
bool deb = 0;
void dk(int r,int s,ll co,int t)
{
    if(deb)cout<<r<<" "<<s<<" "<<co<<" "<<t<<"\n";
    if(t == 0 && r != 0)
    {
        if(co+a < cs[r-1][s][t])
        {
            pq.push({co+a,r-1,s,t});
            cs[r-1][s][t] = co+a;
        }
        if(co+a+c*dis[r-1][s] < cs[r-1][s][4])
        {
            pq.push({co+a+c*dis[r-1][s],r-1,s,4});
            cs[r-1][s][4] = co+a+c*dis[r-1][s];
        }
    }
    else if(t == 1 && s != w-1)
    {
        if(co+a < cs[r][s+1][t])
        {
            pq.push({co+a,r,s+1,t});
            cs[r][s+1][t] = co+a;
        }
        if(co+a+c*dis[r][s+1] < cs[r][s+1][4])
        {
            pq.push({co+a+c*dis[r][s+1],r,s+1,4});
            cs[r][s+1][4] = co+a+c*dis[r][s+1];
        }
    }
    else if(t == 2 && r !=h-1)
    {
        if(co+a < cs[r+1][s][t])
        {
            pq.push({co+a,r+1,s,t});
            cs[r+1][s][t] = co+a;
        }
        if(co+a+c*dis[r+1][s] < cs[r+1][s][4])
        {
            pq.push({co+a+c*dis[r+1][s],r+1,s,4});
            cs[r+1][s][4] = co+a+c*dis[r+1][s];
        }
    }
    else if(t == 3 &&  s != 0)
    {
        if(co+a < cs[r][s-1][t])
        {
            pq.push({co+a,r,s-1,t});
            cs[r][s-1][t] = co+a;
        }
        if(co+a+c*dis[r][s-1] < cs[r][s-1][4])
        {
            pq.push({co+a+c*dis[r][s-1],r,s-1,4});
            cs[r][s-1][4] = co+a+c*dis[r][s-1];
        }
    }
    else if(t == 4)
    {
        rep(i,4)
        {
            if(co+b < cs[r][s][i])
            {
                pq.push({co+b,r,s,i});
                cs[r][s][i] = co+b;
            }
        }
        if(r != 0 && co+c < cs[r-1][s][4])
        {
            pq.push({co+c,r-1,s,4});
            cs[r-1][s][4] = co+c;
        }
        if(deb && r == 1&& s == 4)
        {
            cout<<co+c<<" "<<cs[r][s+1][4]<<"\n\n";
        }
        if(s != w-1 && co+c < cs[r][s+1][4])
        {
            pq.push({co+c,r,s+1,4});
            cs[r][s+1][4] = co+c;
        }
        if(r != h-1 && co+c < cs[r+1][s][4])
        {
            pq.push({co+c,r+1,s,4});
            cs[r+1][s][4] = co+c;
        }
        if(s != 0 && co+c < cs[r][s-1][4])
        {
            pq.push({co+c,r,s-1,4});
            cs[r][s-1][4] = co+c;
        }
    }
    if(deb && cs[1][5][4] == 17)
    {
        cout<<r<<" "<<s<<" "<<t<<" "<<co<<"\n\n";
    }
}
int main()
{
    cin>>h>>w;
    h++;w++;
    dis.resize(h);
    for(int i = 0;i<h;i++)
    {
        dis[i].resize(w);
        for(int j =0 ;j<w;j++)
        {
            dis[i][j] = -1;
            rep(q,5)
            {
                cs[i][j][q] = infl;
            }
        }
    }
    cin>>a>>b>>c;
    int n;
    cin>>n;
    queue<vector<int>> bfs;
    pair<int,int> start;
    pair<int,int> finish;
    for(int i = 0;i<n;i++)
    {
        int s,t;
        cin>>s>>t;

        if(i != n-1)
        {
            bfs.push({0,s,t});
        }
        if(i == 0)
        {
            start = {s,t};
        }
        if(i == n-1)
        {
            finish = {s,t};
        }
        dis[s][t] = 0;
    }
    while(!bfs.empty())
    {
        vector<int> cu = bfs.front();
        int s = cu[1];
        int t = cu[2];
        if( s!= 0 && dis[s-1][t] == -1)
        {
            bfs.push({cu[0]+1,s-1,t});
            dis[s-1][t] = cu[0]+1;
        }
        if( s!= h-1 && dis[s+1][t] == -1)
        {
            bfs.push({cu[0]+1,s+1,t});
            dis[s+1][t] = cu[0]+1;
        }
        if( t!= 0 && dis[s][t-1] == -1)
        {
            bfs.push({cu[0]+1,s,t-1});
            dis[s][t-1] = cu[0]+1;
        }
        if( t!= w-1 && dis[s][t+1] == -1)
        {
            bfs.push({cu[0]+1,s,t+1});
            dis[s][t+1] = cu[0]+1;
        }
        bfs.pop();
    }
    pq.push({0,start.st,start.nd,4});
    cs[start.st][start.nd][4] = 0;
    while(!pq.empty())
    {
        ll c = pq.top()[0],a = pq.top()[1],b = pq.top()[2],t = pq.top()[3];
        pq.pop();
        if(cs[a][b][t] == c)
        {
            dk(a,b,c,t);
        }
    }
    cout<<cs[finish.st][finish.nd][4]<<"\n";
}

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