oj.uz

답안 #536880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536880 2022-03-14T06:38:19 Z 79brue Soccer (JOI17_soccer) C++14
35 / 100
 3000 ms 168356 KB 
#include <bits/stdc++.h>

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 21420 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1244 ms 68632 KB Output is correct
4 Correct 1212 ms 68644 KB Output is correct
5 Correct 305 ms 26416 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2792 ms 167248 KB Output is correct
2 Correct 2703 ms 167408 KB Output is correct
3 Correct 1870 ms 94684 KB Output is correct
4 Correct 1671 ms 68752 KB Output is correct
5 Correct 1855 ms 99896 KB Output is correct
6 Correct 1833 ms 101572 KB Output is correct
7 Correct 2407 ms 168356 KB Output is correct
8 Correct 2454 ms 167900 KB Output is correct
9 Correct 2112 ms 168212 KB Output is correct
10 Correct 231 ms 30464 KB Output is correct
11 Correct 2406 ms 167864 KB Output is correct
12 Correct 2635 ms 167496 KB Output is correct
13 Correct 1650 ms 94668 KB Output is correct
14 Correct 2340 ms 168044 KB Output is correct
15 Correct 1809 ms 166132 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 21420 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1244 ms 68632 KB Output is correct
4 Correct 1212 ms 68644 KB Output is correct
5 Correct 305 ms 26416 KB Output is correct
6 Correct 2792 ms 167248 KB Output is correct
7 Correct 2703 ms 167408 KB Output is correct
8 Correct 1870 ms 94684 KB Output is correct
9 Correct 1671 ms 68752 KB Output is correct
10 Correct 1855 ms 99896 KB Output is correct
11 Correct 1833 ms 101572 KB Output is correct
12 Correct 2407 ms 168356 KB Output is correct
13 Correct 2454 ms 167900 KB Output is correct
14 Correct 2112 ms 168212 KB Output is correct
15 Correct 231 ms 30464 KB Output is correct
16 Correct 2406 ms 167864 KB Output is correct
17 Correct 2635 ms 167496 KB Output is correct
18 Correct 1650 ms 94668 KB Output is correct
19 Correct 2340 ms 168044 KB Output is correct
20 Correct 1809 ms 166132 KB Output is correct
21 Correct 334 ms 25264 KB Output is correct
22 Execution timed out 3052 ms 101776 KB Time limit exceeded
23 Halted 0 ms 0 KB -