oj.uz

Submission #537399

# Submission time Handle Problem Language Result Execution time Memory
537399 2022-03-15T04:53:39 Z 79brue Soccer (JOI17_soccer) C++14
100 / 100
 2759 ms 171152 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
typedef long long ll;
 
struct dat{
    ll x, y, d; int i;
    dat(){}
    dat(ll x, ll y, ll d, int i): x(x), y(y), d(d), i(i){}
};
 
struct cont{
    ll x, y; int d, i; ll dist;
    cont(){}
    cont(ll x, ll y, int d, int i, ll dist): x(x), y(y), d(d), i(i), dist(dist){}
 
    bool operator<(const cont &r)const{
        return dist > r.dist;
    }
};
 
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
 
int n, m, k;
ll a, b, c;
ll x[100002], y[100002];
ll near[502][502][2];
int nearIdx[502][502][2];
ll dist[502][502][5][2];
int distIdx[502][502][5][2];
ll ans = LLONG_MAX;
 
void makeNear(){
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            near[i][j][0] = near[i][j][1] = 1e18;
            nearIdx[i][j][0] = nearIdx[i][j][1] = -1;
            for(int dir=0; dir<5; dir++){
                dist[i][j][dir][0] = dist[i][j][dir][1] = 1e18;
                distIdx[i][j][dir][0] = distIdx[i][j][dir][1] = -1;
            }
        }
    }
 
    queue<dat> que;
    for(int i=1; i<=k; i++){
        que.push(dat(x[i], y[i], 0, i));
        for(int j=0; j<2; j++){
            if(near[x[i]][y[i]][j] == 1e18){
                near[x[i]][y[i]][j] = 0;
                nearIdx[x[i]][y[i]][j] = i;
                break;
            }
        }
    }
 
    while(!que.empty()){
        dat tmp = que.front();
        que.pop();
 
        for(int d=0; d<4; d++){
            int tx = tmp.x+xx[d], ty = tmp.y+yy[d];
            if(!(0<=tx&&tx<=n&&0<=ty&&ty<=m) || nearIdx[tx][ty][1] != -1 || nearIdx[tx][ty][0] == tmp.i) continue;
            int u = 0;
            if(nearIdx[tx][ty][0] != -1) u=1;
            near[tx][ty][u] = tmp.d + 1;
            nearIdx[tx][ty][u] = tmp.i;
            que.push(dat(tx, ty, tmp.d+1, tmp.i));
        }
    }
}
 
int main(){
    scanf("%d %d %lld %lld %lld %d", &n, &m, &a, &b, &c, &k);
    for(int i=1; i<=k; i++) scanf("%lld %lld", &x[i], &y[i]);
    makeNear();
 
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
//            printf("%d %d: %lld %d / %lld %d\n", i, j, near[i][j][0], nearIdx[i][j][0], near[i][j][1], nearIdx[i][j][1]);
        }
    }
 
    priority_queue<cont> pq;
    pq.push(cont(x[1], y[1], 4, 1, 0));
 
    while(!pq.empty()){
        cont tmp = pq.top(); pq.pop();
        if(distIdx[tmp.x][tmp.y][tmp.d][1] != -1 || distIdx[tmp.x][tmp.y][tmp.d][0] == tmp.i) continue;
        int u = (distIdx[tmp.x][tmp.y][tmp.d][0] == -1) ? 0 : 1;
        dist[tmp.x][tmp.y][tmp.d][u] = tmp.dist;
        distIdx[tmp.x][tmp.y][tmp.d][u] = tmp.i;
 
        ans = min(ans, tmp.dist + c * (abs(tmp.x-x[k]) + abs(tmp.y-y[k])));
//        printf("%lld %lld %d %d: %lld\n", tmp.x, tmp.y, tmp.d, u, tmp.dist);
 
        if(tmp.d == 4){ /// 현재 선수가 공을 가지고 있다.
            for(int d=0; d<4; d++){
                ll tx = tmp.x + xx[d], ty = tmp.y + yy[d];
                if(tx<0||tx>n||ty<0||ty>m) continue;
                { /// d번 방향으로 한 칸 이동하기
                    if(distIdx[tx][ty][4][1] != -1 || distIdx[tx][ty][4][0] == tmp.i) continue;
                    pq.push(cont(tx, ty, 4, tmp.i, tmp.dist + c));
                }
                { /// d번 방향으로 공 굴리기
                    if(distIdx[tx][ty][d][1] != -1 || distIdx[tx][ty][d][0] == tmp.i) continue;
                    pq.push(cont(tx, ty, d, tmp.i, tmp.dist + a + b));
                }
            }
        }
        else{
            { /// 공이 계속 굴러가게 하기
                int d = tmp.d;
                ll tx = tmp.x + xx[d], ty = tmp.y + yy[d];
                if(!(tx<0 || tx>n || ty<0 || ty>m)){
                    if(distIdx[tx][ty][d][1] != -1 || distIdx[tx][ty][d][0] == tmp.i) continue;
                    pq.push(cont(tx, ty, d, tmp.i, tmp.dist + a));
                }
            }
            { /// 공을 선수가 잡기
                for(int u=0; u<2; u++){
                    if(tmp.i == nearIdx[tmp.x][tmp.y][u]) continue;
                    pq.push(cont(tmp.x, tmp.y, 4, nearIdx[tmp.x][tmp.y][u], tmp.dist + near[tmp.x][tmp.y][u] * c));
                }
            }
        }
    }
 
    printf("%lld", ans);
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d %lld %lld %lld %d", &n, &m, &a, &b, &c, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:79:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     for(int i=1; i<=k; i++) scanf("%lld %lld", &x[i], &y[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 21500 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 936 ms 68700 KB Output is correct
4 Correct 1022 ms 68732 KB Output is correct
5 Correct 289 ms 26384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2234 ms 167316 KB Output is correct
2 Correct 2159 ms 167376 KB Output is correct
3 Correct 1582 ms 94556 KB Output is correct
4 Correct 1527 ms 68752 KB Output is correct
5 Correct 1680 ms 99900 KB Output is correct
6 Correct 1575 ms 101520 KB Output is correct
7 Correct 2211 ms 168296 KB Output is correct
8 Correct 2198 ms 167652 KB Output is correct
9 Correct 2065 ms 168344 KB Output is correct
10 Correct 254 ms 30428 KB Output is correct
11 Correct 2183 ms 167720 KB Output is correct
12 Correct 2196 ms 167380 KB Output is correct
13 Correct 1473 ms 94692 KB Output is correct
14 Correct 2090 ms 168036 KB Output is correct
15 Correct 1717 ms 166092 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 21500 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 936 ms 68700 KB Output is correct
4 Correct 1022 ms 68732 KB Output is correct
5 Correct 289 ms 26384 KB Output is correct
6 Correct 2234 ms 167316 KB Output is correct
7 Correct 2159 ms 167376 KB Output is correct
8 Correct 1582 ms 94556 KB Output is correct
9 Correct 1527 ms 68752 KB Output is correct
10 Correct 1680 ms 99900 KB Output is correct
11 Correct 1575 ms 101520 KB Output is correct
12 Correct 2211 ms 168296 KB Output is correct
13 Correct 2198 ms 167652 KB Output is correct
14 Correct 2065 ms 168344 KB Output is correct
15 Correct 254 ms 30428 KB Output is correct
16 Correct 2183 ms 167720 KB Output is correct
17 Correct 2196 ms 167380 KB Output is correct
18 Correct 1473 ms 94692 KB Output is correct
19 Correct 2090 ms 168036 KB Output is correct
20 Correct 1717 ms 166092 KB Output is correct
21 Correct 384 ms 25200 KB Output is correct
22 Correct 2529 ms 101648 KB Output is correct
23 Correct 2473 ms 98372 KB Output is correct
24 Correct 2759 ms 102736 KB Output is correct
25 Correct 2128 ms 101708 KB Output is correct
26 Correct 2219 ms 70048 KB Output is correct
27 Correct 717 ms 44800 KB Output is correct
28 Correct 1189 ms 46808 KB Output is correct
29 Correct 1941 ms 73932 KB Output is correct
30 Correct 1012 ms 50492 KB Output is correct
31 Correct 2389 ms 168116 KB Output is correct
32 Correct 2350 ms 171152 KB Output is correct
33 Correct 1631 ms 101580 KB Output is correct
34 Correct 2511 ms 167996 KB Output is correct
35 Correct 724 ms 41604 KB Output is correct