oj.uz

Submission #169141

# Submission time Handle Problem Language Result Execution time Memory
169141 2019-12-18T15:28:11 Z combi1k1 Soccer (JOI17_soccer) C++14
100 / 100
 1170 ms 128632 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

#define all(x)  x.begin(),x.end()
#define sz(x)   (int)x.size()

#define pb      emplace_back
#define endl    "\n"

const ll    inf = 1e18;
const int   N   = 505;

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

typedef pair<ll,int>    ii;

vector<ii>  g[N * N * 5];

int d[N][N];
int S, T;

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int H, W;   cin >> H >> W;
    int A, B;   cin >> A >> B;
    int C;      cin >> C;

    H++;
    W++;

    for(int i = 0 ; i < H ; ++i)
    for(int j = 0 ; j < W ; ++j)
        d[i][j] = -1;

    int n;  cin >> n;

    queue<ii>   qu;

    for(int i = 0 ; i < n ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        d[x][y] = 0;

        qu.push(ii(x,y));

        if (i == 0)     S = (x * W + y) * 5 + 4;
        if (i == n - 1) T = (x * W + y) * 5 + 4;
    }

    while (qu.size())   {
        int x = qu.front().X;
        int y = qu.front().Y;   qu.pop();

        for(int i = 0 ; i < 4 ; ++i)    {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if (xx < 0 || xx >= H)  continue;
            if (yy < 0 || yy >= W)  continue;

            if (d[xx][yy] < 0)  {
                d[xx][yy] = d[x][y] + 1;
                qu.push(ii(xx,yy));
            }
        }
    }

    for(int i = 0 ; i < H ; ++i)
    for(int j = 0 ; j < W ; ++j)
        for(int k = 0 ; k < 4 ; ++k)    {
            int x = i + dx[k];
            int y = j + dy[k];

            int u = (i * W + j) * 5;
            int v = (x * W + y) * 5;

            g[u + k].pb(1ll * C * d[i][j] + B,u + 4);

            if (x < 0 || x >= H)    continue;
            if (y < 0 || y >= W)    continue;

            g[u + 4].pb(C,v + 4);
            g[u + k].pb(A,v + k);
            g[u + 4].pb(A,v + k);
        }

    vector<ll>  dis(H * W * 5 + 5,inf);

    priority_queue<ii,vector<ii>,greater<ii> >  pq;

    pq.push(ii(0,S));   dis[S] = 0;

    while (pq.size())   {
        int u  = pq.top().Y;
        ll  du = pq.top().X;

        pq.pop();

        if (du != dis[u])
            continue;

        for(ii  e : g[u])   {
            int v = e.Y;
            ll  C = e.X;

            if (dis[v] > du + C)    {
                dis[v] = du + C;

                pq.push(ii(dis[v],v));
            }
        }
    }

    cout << dis[T] << endl;
}
/*
6 5
1 3 6
3
1 1
0 4
6 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 54388 KB Output is correct
2 Correct 29 ms 30328 KB Output is correct
3 Correct 787 ms 127848 KB Output is correct
4 Correct 832 ms 127948 KB Output is correct
5 Correct 215 ms 64880 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 127804 KB Output is correct
2 Correct 821 ms 127848 KB Output is correct
3 Correct 598 ms 109256 KB Output is correct
4 Correct 678 ms 127848 KB Output is correct
5 Correct 631 ms 109544 KB Output is correct
6 Correct 700 ms 127912 KB Output is correct
7 Correct 817 ms 127876 KB Output is correct
8 Correct 759 ms 127848 KB Output is correct
9 Correct 813 ms 127840 KB Output is correct
10 Correct 139 ms 47348 KB Output is correct
11 Correct 837 ms 127852 KB Output is correct
12 Correct 825 ms 127848 KB Output is correct
13 Correct 550 ms 109220 KB Output is correct
14 Correct 821 ms 127852 KB Output is correct
15 Correct 643 ms 109516 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 54388 KB Output is correct
2 Correct 29 ms 30328 KB Output is correct
3 Correct 787 ms 127848 KB Output is correct
4 Correct 832 ms 127948 KB Output is correct
5 Correct 215 ms 64880 KB Output is correct
6 Correct 817 ms 127804 KB Output is correct
7 Correct 821 ms 127848 KB Output is correct
8 Correct 598 ms 109256 KB Output is correct
9 Correct 678 ms 127848 KB Output is correct
10 Correct 631 ms 109544 KB Output is correct
11 Correct 700 ms 127912 KB Output is correct
12 Correct 817 ms 127876 KB Output is correct
13 Correct 759 ms 127848 KB Output is correct
14 Correct 813 ms 127840 KB Output is correct
15 Correct 139 ms 47348 KB Output is correct
16 Correct 837 ms 127852 KB Output is correct
17 Correct 825 ms 127848 KB Output is correct
18 Correct 550 ms 109220 KB Output is correct
19 Correct 821 ms 127852 KB Output is correct
20 Correct 643 ms 109516 KB Output is correct
21 Correct 230 ms 64848 KB Output is correct
22 Correct 973 ms 127876 KB Output is correct
23 Correct 938 ms 116576 KB Output is correct
24 Correct 1024 ms 126008 KB Output is correct
25 Correct 916 ms 128016 KB Output is correct
26 Correct 896 ms 127968 KB Output is correct
27 Correct 566 ms 124392 KB Output is correct
28 Correct 655 ms 124600 KB Output is correct
29 Correct 850 ms 126584 KB Output is correct
30 Correct 616 ms 124664 KB Output is correct
31 Correct 921 ms 127852 KB Output is correct
32 Correct 1087 ms 128632 KB Output is correct
33 Correct 777 ms 127976 KB Output is correct
34 Correct 1170 ms 128080 KB Output is correct
35 Correct 574 ms 124712 KB Output is correct