oj.uz

Submission #50281

# Submission time Handle Problem Language Result Execution time Memory
50281 2018-06-09T06:43:05 Z gs13105 Soccer (JOI17_soccer) C++17
100 / 100
 1163 ms 131756 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 61884 KB Output is correct
2 Correct 40 ms 61884 KB Output is correct
3 Correct 849 ms 127640 KB Output is correct
4 Correct 905 ms 127748 KB Output is correct
5 Correct 257 ms 127748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 127808 KB Output is correct
2 Correct 1016 ms 127896 KB Output is correct
3 Correct 738 ms 127896 KB Output is correct
4 Correct 799 ms 128072 KB Output is correct
5 Correct 804 ms 128072 KB Output is correct
6 Correct 811 ms 128072 KB Output is correct
7 Correct 1022 ms 128072 KB Output is correct
8 Correct 937 ms 128072 KB Output is correct
9 Correct 1083 ms 128260 KB Output is correct
10 Correct 185 ms 128260 KB Output is correct
11 Correct 1036 ms 128260 KB Output is correct
12 Correct 1043 ms 128260 KB Output is correct
13 Correct 654 ms 128260 KB Output is correct
14 Correct 1006 ms 128300 KB Output is correct
15 Correct 849 ms 128300 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 61884 KB Output is correct
2 Correct 40 ms 61884 KB Output is correct
3 Correct 849 ms 127640 KB Output is correct
4 Correct 905 ms 127748 KB Output is correct
5 Correct 257 ms 127748 KB Output is correct
6 Correct 1032 ms 127808 KB Output is correct
7 Correct 1016 ms 127896 KB Output is correct
8 Correct 738 ms 127896 KB Output is correct
9 Correct 799 ms 128072 KB Output is correct
10 Correct 804 ms 128072 KB Output is correct
11 Correct 811 ms 128072 KB Output is correct
12 Correct 1022 ms 128072 KB Output is correct
13 Correct 937 ms 128072 KB Output is correct
14 Correct 1083 ms 128260 KB Output is correct
15 Correct 185 ms 128260 KB Output is correct
16 Correct 1036 ms 128260 KB Output is correct
17 Correct 1043 ms 128260 KB Output is correct
18 Correct 654 ms 128260 KB Output is correct
19 Correct 1006 ms 128300 KB Output is correct
20 Correct 849 ms 128300 KB Output is correct
21 Correct 262 ms 128300 KB Output is correct
22 Correct 1083 ms 128300 KB Output is correct
23 Correct 983 ms 128300 KB Output is correct
24 Correct 1087 ms 128300 KB Output is correct
25 Correct 930 ms 128300 KB Output is correct
26 Correct 1138 ms 128300 KB Output is correct
27 Correct 802 ms 128300 KB Output is correct
28 Correct 803 ms 128300 KB Output is correct
29 Correct 898 ms 128320 KB Output is correct
30 Correct 708 ms 128320 KB Output is correct
31 Correct 1064 ms 131064 KB Output is correct
32 Correct 1163 ms 131756 KB Output is correct
33 Correct 827 ms 131756 KB Output is correct
34 Correct 1096 ms 131756 KB Output is correct
35 Correct 685 ms 131756 KB Output is correct