oj.uz

Submission #205610

# Submission time Handle Problem Language Result Execution time Memory
205610 2020-02-29T10:02:27 Z Kastanda Soccer (JOI17_soccer) C++11
100 / 100
 533 ms 19820 KB 
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 505, MXN = 100005;
int n, m, k, A, B, C, P[N][N];
pair < int , int > At[MXN];
long long D[N][N][5];
int gx[] = {-1, 1, 0, 0};
int gy[] = {0, 0, -1, 1};
int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d", &A, &B, &C);
    scanf("%d", &k);
    memset(P, 63, sizeof(P));
    queue < pair < int , int > > qu;
    for (int i = 1; i <= k; i ++)
    {
        scanf("%d%d", &At[i].first, &At[i].second);
        P[At[i].first][At[i].second] = 0;
        if (i < k) qu.push({At[i].first, At[i].second});
    }
    while (qu.size())
    {
        int a = qu.front().first;
        int b = qu.front().second;
        qu.pop();
        for (int h = 0; h < 4; h ++)
        {
            int ta = a + gx[h];
            int tb = b + gy[h];
            if (ta >= 0 && ta <= n && tb >= 0 && tb <= m && P[ta][tb] > P[a][b] + 1)
                P[ta][tb] = P[a][b] + 1, qu.push({ta, tb});
        }
    }
    P[At[k].first][At[k].second] = 0;
    memset(D, 63, sizeof(D));
    priority_queue < tuple < long long , int , int , int > > Pq;
    auto Relax = [&] (int a, int b, int w, long long d) {
        if (D[a][b][w] > d) {
            D[a][b][w] = d;
            Pq.push(make_tuple(-d, a, b, w));
        }
    };
    Relax(At[1].first, At[1].second, 4, 0);
    while (Pq.size())
    {
        long long d;
        int a, b, w;
        tie(d, a, b, w) = Pq.top();
        Pq.pop(); d = -d;
        if (d > D[a][b][w])
            continue;
        if (w < 4)
        {
            int ta = a + gx[w], tb = b + gy[w];
            if (ta >= 0 && ta <= n && tb >= 0 && tb <= m)
                Relax(ta, tb, w, d + A);
            Relax(a, b, 4, d + 1LL * P[a][b] * C);
        }
        else
        {
            for (int h = 0; h < 4; h ++)
            {
                int ta = a + gx[h], tb = b + gy[h];
                if (ta >= 0 && ta <= n && tb >= 0 && tb <= m)
                    Relax(ta, tb, 4, d + C);
                Relax(a, b, h, d + B);
            }
        }
    }
    long long Mn = LLONG_MAX;
    for (int h = 0; h <= 4; h ++)
        Mn = min(Mn, D[At[k].first][At[k].second][h]);
    return !printf("%lld\n", Mn);
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &A, &B, &C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
soccer.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &At[i].first, &At[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 12912 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 360 ms 17636 KB Output is correct
4 Correct 395 ms 17640 KB Output is correct
5 Correct 94 ms 11384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 17648 KB Output is correct
2 Correct 429 ms 17656 KB Output is correct
3 Correct 317 ms 17644 KB Output is correct
4 Correct 305 ms 17640 KB Output is correct
5 Correct 336 ms 17656 KB Output is correct
6 Correct 334 ms 17768 KB Output is correct
7 Correct 402 ms 17936 KB Output is correct
8 Correct 359 ms 17680 KB Output is correct
9 Correct 426 ms 17680 KB Output is correct
10 Correct 71 ms 13088 KB Output is correct
11 Correct 400 ms 17676 KB Output is correct
12 Correct 415 ms 17664 KB Output is correct
13 Correct 247 ms 17636 KB Output is correct
14 Correct 417 ms 17684 KB Output is correct
15 Correct 305 ms 17684 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 12912 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 360 ms 17636 KB Output is correct
4 Correct 395 ms 17640 KB Output is correct
5 Correct 94 ms 11384 KB Output is correct
6 Correct 431 ms 17648 KB Output is correct
7 Correct 429 ms 17656 KB Output is correct
8 Correct 317 ms 17644 KB Output is correct
9 Correct 305 ms 17640 KB Output is correct
10 Correct 336 ms 17656 KB Output is correct
11 Correct 334 ms 17768 KB Output is correct
12 Correct 402 ms 17936 KB Output is correct
13 Correct 359 ms 17680 KB Output is correct
14 Correct 426 ms 17680 KB Output is correct
15 Correct 71 ms 13088 KB Output is correct
16 Correct 400 ms 17676 KB Output is correct
17 Correct 415 ms 17664 KB Output is correct
18 Correct 247 ms 17636 KB Output is correct
19 Correct 417 ms 17684 KB Output is correct
20 Correct 305 ms 17684 KB Output is correct
21 Correct 97 ms 11844 KB Output is correct
22 Correct 485 ms 17648 KB Output is correct
23 Correct 463 ms 14592 KB Output is correct
24 Correct 510 ms 14636 KB Output is correct
25 Correct 416 ms 17660 KB Output is correct
26 Correct 471 ms 17828 KB Output is correct
27 Correct 304 ms 13316 KB Output is correct
28 Correct 290 ms 13908 KB Output is correct
29 Correct 415 ms 16756 KB Output is correct
30 Correct 247 ms 13688 KB Output is correct
31 Correct 424 ms 17812 KB Output is correct
32 Correct 523 ms 19820 KB Output is correct
33 Correct 341 ms 17632 KB Output is correct
34 Correct 533 ms 17684 KB Output is correct
35 Correct 247 ms 13820 KB Output is correct