oj.uz

Submission #87929

# Submission time Handle Problem Language Result Execution time Memory
87929 2018-12-03T08:52:30 Z tieunhi Soccer (JOI17_soccer) C++14
100 / 100
 664 ms 26400 KB 
#include <bits/stdc++.h>
#define pii pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define N 505
#define MM 100005
#define LN 19
#define maxc 1000000007

using namespace std;

int n, m, A, B, C, k;
pii pp[MM];
ll dist[N][N], d[N][N][5];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void setup()
{
    cin >> n >> m >> A >> B >> C; n++; m++;
    cin >> k;
    FOR(i, 1, k)
    {
        int u, v; cin >> u >> v; u++; v++;
        pp[i] = mp(u, v);
    }
}
void prepare()
{
    FOR(i, 0, n+1)
        FOR(j, 0, m+1) dist[i][j] = (1ll << 60);
    queue<pii> q;
    FOR(i, 1, k)
    {
        dist[pp[i].F][pp[i].S] = 0;
        q.push(pp[i]);
    }
    while (!q.empty())
    {
        auto z = q.front(); q.pop();
        FOR(i, 1, 4)
        {
            int x = z.F + dx[i];
            int y = z.S + dy[i];
            if (x > 0 && y > 0 && x <= n && y <= m && dist[x][y] == (1ll << 60))
            {
                dist[x][y] = dist[z.F][z.S] + C;
                q.push(mp(x, y));
            }
        }
    }
}
void solve()
{
    priority_queue<pair<ll, pair<pii, int> > >q;
    FOR(i, 1, n)
        FOR(j, 1, m)
            FOR(k, 0, 4) d[i][j][k] = (1ll << 60);
    q.push(mp(0, mp(mp(pp[1].F, pp[1].S), 0)));
    d[pp[1].F][pp[1].S][0] = 0;
    while (!q.empty())
    {
        auto z = q.top(); q.pop();
        int u = z.S.F.F;
        int v = z.S.F.S;
        int dir = z.S.S;
        ll len = -z.F;
        if (d[u][v][dir] < len) continue;
        if (dir == 0)
        {
            FOR(i, 1, 4)
                if (d[u][v][i] > d[u][v][0] + B)
                {
                    d[u][v][i] = d[u][v][0] + B;
                    q.push(mp(-d[u][v][i], mp(mp(u, v), i)));
                }
            FOR(i, 1, 4)
            {
                int x = u + dx[i];
                int y = v + dy[i];
                if (d[x][y][0] > d[u][v][0] + C)
                {
                    d[x][y][0] = d[u][v][0] + C;
                    q.push(mp(-d[x][y][0], mp(mp(x, y), 0)));
                }
            }
        }
        else
        {
            if (d[u][v][0] > d[u][v][dir] + dist[u][v])
            {
                d[u][v][0] = d[u][v][dir] + dist[u][v];
                q.push(mp(-d[u][v][0], mp(mp(u, v), 0)));
            }
            int x = u + dx[dir];
            int y = v + dy[dir];
            if (d[x][y][dir] > d[u][v][dir] + A)
            {
                d[x][y][dir] = d[u][v][dir] + A;
                q.push(mp(-d[x][y][dir], mp(mp(x, y), dir)));
            }
        }
    }
    ll res = 1ll << 60;
    FOR(i, 0, 4) res = min(res, d[pp[k].F][pp[k].S][i]);
    cout <<res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    setup();
    prepare();
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7280 KB Output is correct
2 Correct 2 ms 7280 KB Output is correct
3 Correct 452 ms 20656 KB Output is correct
4 Correct 490 ms 20700 KB Output is correct
5 Correct 102 ms 20700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 20760 KB Output is correct
2 Correct 562 ms 20780 KB Output is correct
3 Correct 422 ms 20780 KB Output is correct
4 Correct 371 ms 20920 KB Output is correct
5 Correct 354 ms 20920 KB Output is correct
6 Correct 380 ms 20920 KB Output is correct
7 Correct 472 ms 21060 KB Output is correct
8 Correct 485 ms 21060 KB Output is correct
9 Correct 474 ms 21060 KB Output is correct
10 Correct 74 ms 21060 KB Output is correct
11 Correct 459 ms 21060 KB Output is correct
12 Correct 537 ms 21060 KB Output is correct
13 Correct 308 ms 21060 KB Output is correct
14 Correct 539 ms 21060 KB Output is correct
15 Correct 442 ms 21060 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7280 KB Output is correct
2 Correct 2 ms 7280 KB Output is correct
3 Correct 452 ms 20656 KB Output is correct
4 Correct 490 ms 20700 KB Output is correct
5 Correct 102 ms 20700 KB Output is correct
6 Correct 532 ms 20760 KB Output is correct
7 Correct 562 ms 20780 KB Output is correct
8 Correct 422 ms 20780 KB Output is correct
9 Correct 371 ms 20920 KB Output is correct
10 Correct 354 ms 20920 KB Output is correct
11 Correct 380 ms 20920 KB Output is correct
12 Correct 472 ms 21060 KB Output is correct
13 Correct 485 ms 21060 KB Output is correct
14 Correct 474 ms 21060 KB Output is correct
15 Correct 74 ms 21060 KB Output is correct
16 Correct 459 ms 21060 KB Output is correct
17 Correct 537 ms 21060 KB Output is correct
18 Correct 308 ms 21060 KB Output is correct
19 Correct 539 ms 21060 KB Output is correct
20 Correct 442 ms 21060 KB Output is correct
21 Correct 111 ms 21060 KB Output is correct
22 Correct 660 ms 21060 KB Output is correct
23 Correct 647 ms 21060 KB Output is correct
24 Correct 664 ms 21060 KB Output is correct
25 Correct 522 ms 21092 KB Output is correct
26 Correct 556 ms 21352 KB Output is correct
27 Correct 329 ms 21352 KB Output is correct
28 Correct 317 ms 21352 KB Output is correct
29 Correct 486 ms 21352 KB Output is correct
30 Correct 281 ms 21352 KB Output is correct
31 Correct 509 ms 23872 KB Output is correct
32 Correct 630 ms 26400 KB Output is correct
33 Correct 417 ms 26400 KB Output is correct
34 Correct 659 ms 26400 KB Output is correct
35 Correct 267 ms 26400 KB Output is correct