Submission #50281

#	Time	Username	Problem	Language	Result	Execution time	Memory
50281		gs13105	Soccer (JOI17_soccer)	C++17	100 / 100	1163 ms	131756 KiB

soccer

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

struct edg
{
    int x;
    long long w;
    bool operator <(const edg &e) const
    {
        return w > e.w;
    }
};

int dis[510][510];

long long mem[1260000];
vector<edg> arr[1260000];

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

inline int idx(int t, int x, int y)
{
    return t * (h + 1) * (w + 1) + x * (w + 1) + y;
}

inline void add_edge(int x, int y, long long w)
{
    arr[x].push_back({ y, w });
}

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int a, b, c, n, s, g, i, j, d;
    scanf("%d%d%d%d%d%d", &h, &w, &a, &b, &c, &n);

    queue<int> q1;
    memset(dis, -1, sizeof dis);
    for(i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        dis[x][y] = 0;
        q1.push(x * (w + 1) + y);

        if(i == 1)
            s = idx(4, x, y);
        if(i == n)
            g = idx(4, x, y);
    }

    for(i = 1; !q1.empty(); i++)
    {
        int sz = q1.size();
        for(j = 0; j < sz; j++)
        {
            int x = q1.front() / (w + 1);
            int y = q1.front() % (w + 1);
            q1.pop();

            for(d = 0; d < 4; d++)
            {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if(0 <= nx && nx <= h && 0 <= ny && ny <= w && dis[nx][ny] == -1)
                {
                    dis[nx][ny] = i;
                    q1.push(nx * (w + 1) + ny);
                }
            }
        }
    }

    for(i = 0; i <= h; i++)
    {
        for(j = 0; j <= w; j++)
        {
            for(d = 0; d < 4; d++)
            {
                add_edge(idx(4, i, j), idx(d, i, j), b);
                add_edge(idx(d, i, j), idx(4, i, j), 1LL * c * dis[i][j]);

                int nx = i + dx[d];
                int ny = j + dy[d];
                if(0 <= nx && nx <= h && 0 <= ny && ny <= w)
                {
                    add_edge(idx(4, i, j), idx(4, nx, ny), c);
                    add_edge(idx(d, i, j), idx(d, nx, ny), a);
                }
            }
        }
    }

    priority_queue<edg> pq;
    memset(mem, -1, sizeof mem);
    mem[s] = 0;
    pq.push({ s, 0 });
    while(!pq.empty())
    {
        int x = pq.top().x;
        long long w = pq.top().w;
        pq.pop();

        if(mem[x] < w)
            continue;

        for(edg &e : arr[x])
        {
            long long nw = w + e.w;
            if(mem[e.x] == -1 || nw < mem[e.x])
            {
                mem[e.x] = nw;
                pq.push({ e.x, nw });
            }
        }
    }
    printf("%lld\n", mem[g]);
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d", &h, &w, &a, &b, &c, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:137:11: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%lld\n", mem[g]);
     ~~~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:117:12: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({ s, 0 });
     ~~~~~~~^~~~~~~~~~

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