oj.uz

답안 #1109115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109115 2024-11-06T04:12:45 Z nh0902 악어의 지하 도시 (IOI11_crocodile) C++14
100 / 100
 380 ms 96448 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 110000;

long long const inf = 1e16;

vector<pair<int, long long>> g[N];

vector<int> Exit;

int trace1[N], trace2[N];

long long min_dist1[N], min_dist2[N];

bool update(int x, int i, long long d) {
    if (x == trace2[i]) {
        if (min_dist2[i] <= d) {
            return false;
        }
        min_dist2[i] = d;
        if (min_dist1[i] > min_dist2[i]) {
            swap(min_dist1[i], min_dist2[i]);
            swap(trace1[i], trace2[i]);
        }
        return true;
    }

    if (x == trace1[i]) {
        if (min_dist1[i] <= d) {
            return false;
        }
        min_dist1[i] = d;
        return true;
    }

    if (min_dist2[i] <= d) {
        return false;
    }
    min_dist2[i] = d;
    trace2[i] = x;
    if (min_dist1[i] > min_dist2[i]) {
        swap(min_dist1[i], min_dist2[i]);
        swap(trace1[i], trace2[i]);
    }
    return true;
}

int travel_plan(int n, int m, int r[][2], int w[], int k, int e[]) {
    for (int i = 0; i < m; i ++) {
        g[r[i][0]].push_back({r[i][1], w[i]});
        g[r[i][1]].push_back({r[i][0], w[i]});
    }

    for (int i = 0; i < k; i ++) {
        Exit.push_back(e[i]);
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    for (int i = 0; i < n; i ++) {
        min_dist1[i] = min_dist2[i] = inf;
        trace1[i] = n;
        trace2[i] = n;
    }

    for (int a : Exit) {
        min_dist1[a] = min_dist2[a] = 0;
        trace1[a] = a;
        trace2[a] = a;
        pq.push({0, a});
    }

    int x;
    long long d;

    while (!pq.empty()) {
        auto [d, x] = pq.top();
        pq.pop();

        if (d > min_dist2[x]) continue;

        for (pair<int, long long> e : g[x]) {
            if (update(x, e.first, d + e.second)) {
                if (min_dist2[e.first] < inf) {
                    pq.push({min_dist2[e.first], e.first});
                }
            }
        }
    }

    return min_dist2[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |         auto [d, x] = pq.top();
      |              ^
crocodile.cpp:75:9: warning: unused variable 'x' [-Wunused-variable]
   75 |     int x;
      |         ^
crocodile.cpp:76:15: warning: unused variable 'd' [-Wunused-variable]
   76 |     long long d;
      |               ^

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8652 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 3 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 3 ms 8528 KB Output is correct
8 Correct 2 ms 8524 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8652 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 3 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 3 ms 8528 KB Output is correct
8 Correct 2 ms 8524 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 2 ms 8956 KB Output is correct
12 Correct 5 ms 9208 KB Output is correct
13 Correct 5 ms 9308 KB Output is correct
14 Correct 2 ms 8528 KB Output is correct
15 Correct 3 ms 8672 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8652 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 3 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 3 ms 8528 KB Output is correct
8 Correct 2 ms 8524 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 2 ms 8956 KB Output is correct
12 Correct 5 ms 9208 KB Output is correct
13 Correct 5 ms 9308 KB Output is correct
14 Correct 2 ms 8528 KB Output is correct
15 Correct 3 ms 8672 KB Output is correct
16 Correct 328 ms 89896 KB Output is correct
17 Correct 54 ms 21928 KB Output is correct
18 Correct 70 ms 24240 KB Output is correct
19 Correct 380 ms 96448 KB Output is correct
20 Correct 208 ms 74568 KB Output is correct
21 Correct 26 ms 14152 KB Output is correct
22 Correct 222 ms 71496 KB Output is correct