oj.uz

Submission #253376

# Submission time Handle Problem Language Result Execution time Memory
253376 2020-07-27T19:26:14 Z Tuk1352 Soccer (JOI17_soccer) C++11
100 / 100
 620 ms 36072 KB 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int H, W, n;
    cin >> H >> W;
    long long A, B, C;
    cin >> A >> B >> C >> n;
    long long Y[n], X[n];
    long long D[5][H+1][W+1], G[5][H+1][W+1], Di[H+1][W+1], Gd[H+1][W+1];
    for (int y = 0; y <= H; y++)
    {
        for (int u = 0; u <= W; u++)
        {
            Di[y][u] = 2000000000000;
            Gd[y][u] = 1;
            for (int i = 0; i < 5; i++)
            {
                D[i][y][u] = 2000000000000000000;
                G[i][y][u] = 1;
            }
        }
    }
    vector <pair<int,int>> T;
    for (int i = 0; i < n; i++)
    {
        cin >> Y[i] >> X[i];
        Di[Y[i]][X[i]] = 0;
        if (Gd[Y[i]][X[i]] == 1)
        {
            Gd[Y[i]][X[i]] = 0;
            T.push_back({Y[i],X[i]});
        }
    }
    for (int i = 0; i < T.size(); i++)
    {
        int I = T[i].first;
        int Y = T[i].second;
        if (I > 0 && Gd[I-1][Y] == 1)
        {
            Gd[I-1][Y] = 0;
            Di[I-1][Y] = Di[I][Y] + 1;
            T.push_back({I-1,Y});
        }
        if (Y > 0 && Gd[I][Y-1] == 1)
        {
            Gd[I][Y-1] = 0;
            Di[I][Y-1] = Di[I][Y] + 1;
            T.push_back({I,Y-1});
        }
        if (I <= H-1 && Gd[I+1][Y] == 1)
        {
            Gd[I+1][Y] = 0;
            Di[I+1][Y] = Di[I][Y] + 1;
            T.push_back({I+1,Y});
        }
        if (Y <= W-1 && Gd[I][Y+1] == 1)
        {
            Gd[I][Y+1] = 0;
            Di[I][Y+1] = Di[I][Y] + 1;
            T.push_back({I,Y+1});
        }
    }
    priority_queue <pair<pair<long long, int>,pair<int, int>>, vector<pair<pair<long long, int>,pair<int, int>>>, greater<pair<pair<long long, int>,pair<int, int>>>> Q;
    D[0][Y[0]][X[0]] = 0;
    Q.push({{0,0},{Y[0],X[0]}});
    while (Q.size() > 0)
    {
        int I = Q.top().second.first;
        int Y = Q.top().second.second;
        int d = Q.top().first.first;
        int t = Q.top().first.second;
        Q.pop();
        if (G[t][I][Y] == 0)
        {
            continue;
        }
        G[t][I][Y] = 0;
        if (t == 0)
        {
            if (I > 0 && D[0][I][Y] + C < D[0][I-1][Y])
            {
                D[0][I-1][Y] = D[0][I][Y] + C;
                Q.push({{D[0][I-1][Y],0},{I-1,Y}});
            }
            if (Y > 0 && D[0][I][Y] + C < D[0][I][Y-1])
            {
                D[0][I][Y-1] = D[0][I][Y] + C;
                Q.push({{D[0][I][Y-1],0},{I,Y-1}});
            }
            if (I <= H-1 && D[0][I][Y] + C < D[0][I+1][Y])
            {
                D[0][I+1][Y] = D[0][I][Y] + C;
                Q.push({{D[0][I+1][Y],0},{I+1,Y}});
            }
            if (Y <= W-1 && D[0][I][Y] + C < D[0][I][Y+1])
            {
                D[0][I][Y+1] = D[0][I][Y] + C;
                Q.push({{D[0][I][Y+1],0},{I,Y+1}});
            }
            for (int i = 1; i <= 4; i++)
            {
                if (D[0][I][Y] + B < D[i][I][Y])
                {
                    D[i][I][Y] = D[0][I][Y] + B;
                    Q.push({{D[i][I][Y],i},{I,Y}});
                }
            }
        }
        else
        {
            if (D[t][I][Y] + Di[I][Y]*C < D[0][I][Y])
            {
                D[0][I][Y] = D[t][I][Y] + Di[I][Y]*C;
                Q.push({{D[0][I][Y],0},{I,Y}});
            }
            if (t == 1)
            {
                if (I > 0 && D[t][I][Y] + A < D[t][I-1][Y])
                {
                    D[t][I-1][Y] = D[t][I][Y] + A;
                    Q.push({{D[t][I-1][Y],t},{I-1,Y}});
                }
            }
            else if (t == 2)
            {
                if (Y <= W-1 && D[t][I][Y] + A < D[t][I][Y+1])
                {
                    D[t][I][Y+1] = D[t][I][Y] + A;
                    Q.push({{D[t][I][Y+1],t},{I,Y+1}});
                }
            }
            else if (t == 3)
            {
                if (I <= H-1 && D[t][I][Y] + A < D[t][I+1][Y])
                {
                    D[t][I+1][Y] = D[t][I][Y] + A;
                    Q.push({{D[t][I+1][Y],t},{I+1,Y}});
                }
            }
            else if (t == 4)
            {
                if (Y > 0 && D[t][I][Y] + A < D[t][I][Y-1])
                {
                    D[t][I][Y-1] = D[t][I][Y] + A;
                    Q.push({{D[t][I][Y-1],t},{I,Y-1}});
                }
            }
        }
    }
    long long Re = D[0][Y[n-1]][X[n-1]];
    for (int i = 1; i <= 4; i++)
    {
        Re = min(Re, D[i][Y[n-1]][X[n-1]]);
    }
    cout << Re;
    return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < T.size(); i++)
                     ~~^~~~~~~~~~
soccer.cpp:72:13: warning: unused variable 'd' [-Wunused-variable]
         int d = Q.top().first.first;
             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8440 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 358 ms 33632 KB Output is correct
4 Correct 366 ms 33632 KB Output is correct
5 Correct 85 ms 10108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 33632 KB Output is correct
2 Correct 420 ms 33636 KB Output is correct
3 Correct 326 ms 28512 KB Output is correct
4 Correct 314 ms 33632 KB Output is correct
5 Correct 293 ms 28512 KB Output is correct
6 Correct 336 ms 33632 KB Output is correct
7 Correct 392 ms 33632 KB Output is correct
8 Correct 377 ms 33632 KB Output is correct
9 Correct 385 ms 33632 KB Output is correct
10 Correct 57 ms 6392 KB Output is correct
11 Correct 406 ms 33632 KB Output is correct
12 Correct 382 ms 33628 KB Output is correct
13 Correct 262 ms 28512 KB Output is correct
14 Correct 381 ms 33632 KB Output is correct
15 Correct 322 ms 28520 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8440 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 358 ms 33632 KB Output is correct
4 Correct 366 ms 33632 KB Output is correct
5 Correct 85 ms 10108 KB Output is correct
6 Correct 433 ms 33632 KB Output is correct
7 Correct 420 ms 33636 KB Output is correct
8 Correct 326 ms 28512 KB Output is correct
9 Correct 314 ms 33632 KB Output is correct
10 Correct 293 ms 28512 KB Output is correct
11 Correct 336 ms 33632 KB Output is correct
12 Correct 392 ms 33632 KB Output is correct
13 Correct 377 ms 33632 KB Output is correct
14 Correct 385 ms 33632 KB Output is correct
15 Correct 57 ms 6392 KB Output is correct
16 Correct 406 ms 33632 KB Output is correct
17 Correct 382 ms 33628 KB Output is correct
18 Correct 262 ms 28512 KB Output is correct
19 Correct 381 ms 33632 KB Output is correct
20 Correct 322 ms 28520 KB Output is correct
21 Correct 106 ms 10352 KB Output is correct
22 Correct 573 ms 33672 KB Output is correct
23 Correct 525 ms 28168 KB Output is correct
24 Correct 620 ms 30568 KB Output is correct
25 Correct 474 ms 33632 KB Output is correct
26 Correct 544 ms 33816 KB Output is correct
27 Correct 352 ms 27760 KB Output is correct
28 Correct 351 ms 28396 KB Output is correct
29 Correct 448 ms 32872 KB Output is correct
30 Correct 303 ms 28400 KB Output is correct
31 Correct 441 ms 33632 KB Output is correct
32 Correct 566 ms 36072 KB Output is correct
33 Correct 360 ms 33636 KB Output is correct
34 Correct 569 ms 33632 KB Output is correct
35 Correct 260 ms 28404 KB Output is correct