oj.uz

Submission #704859

# Submission time Handle Problem Language Result Execution time Memory
704859 2023-03-03T05:53:17 Z prarie Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 56 ms 4548 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1E12;
int used[50505];
vector<array<int, 4>> edges;

vector<ll> dijkstra(int N, int start, vector<vector<array<int, 4>>> &adj, int p = 0) {
    vector<ll> dist(N, INF);
    vector<int> check(N, 0);
    vector<int> prv(N, -1);
    dist[start] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    for (int rep = 0; rep < N; rep++) {
        int cur = -1;
        ll totalCost = INF;
        for (int i = 0; i < N; i++) {
            if (!check[i] && dist[i] < totalCost) {
                cur = i;
                totalCost = dist[i];
            }
        }
        if (cur == -1) {
            break;
        }
        check[cur] = 1;

        for (auto &[nxt, cst, _, idx] : adj[cur]) {
            if (dist[nxt] > dist[cur] + cst) {
                dist[nxt] = dist[cur] + cst;
                prv[nxt] = idx;
            }
        }
    }

    if (p && dist[N - 1 - start] != INF) {
        for (int cur = N - 1 - start; prv[cur] != -1; cur = edges[prv[cur]][0]) {
            used[prv[cur]] = 1;
        }
    }

    return dist;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<array<int, 4>>> adj(N), rev(N);
    for (int i = 0; i < M; i++) {
        int x, y, z, w;
        cin >> x >> y >> z >> w;
        x--; y--;
        edges.push_back({ x, y, z, w });
        adj[x].push_back({ y, z, w, i });
        rev[y].push_back({ x, z, w, i });
    }

    // dist0 : 0 -> i
    // dist1 : N - 1 - > i
    // dist2 : i -> 0
    // dist3 : i -> N - 1
    auto dist0 = dijkstra(N, 0, adj, 1);
    auto dist1 = dijkstra(N, N - 1, adj, 1);
    auto dist2 = dijkstra(N, 0, rev);
    auto dist3 = dijkstra(N, N - 1, rev);
    const ll ML = 1200000000;
    ll ans = dist0[N - 1] + dist1[0];
    for (int i = 0; i < M; i++) {
        auto &[u, v, cst, inv] = edges[i];
        if (used[i]) {
            adj[u].erase(find_if(adj[u].begin(), adj[u].end(), [&](const array<int, 4> &x) {
                return x[3] == i;
            }));
            adj[v].push_back({ u, cst, inv, i });
            auto p = dijkstra(N, 0, adj);
            auto q = dijkstra(N, N - 1, adj);
            adj[u].push_back({ v, cst, inv, i });
            adj[v].erase(find_if(adj[v].begin(), adj[v].end(), [&](const array<int, 4> &x) {
                return x[3] == i;
            }));
            ans = min(ans, p[N - 1] + q[0] + inv);
            continue;
        }
        int c_ = cst + inv;
        ans = min(ans, min(dist0[N - 1], dist0[v] + dist3[u] + c_) + min(dist1[v] + dist2[u] + c_, dist1[0]));
    }

    if (ans > ML) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 43 ms 468 KB Output is correct
11 Correct 56 ms 340 KB Output is correct
12 Correct 53 ms 436 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4040 KB Output is correct
2 Correct 22 ms 4032 KB Output is correct
3 Correct 30 ms 4028 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 392 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Incorrect 20 ms 3872 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 396 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 3688 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 20 ms 4200 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 19 ms 4548 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 43 ms 468 KB Output is correct
11 Correct 56 ms 340 KB Output is correct
12 Correct 53 ms 436 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -