oj.uz

Submission #485260

# Submission time Handle Problem Language Result Execution time Memory
485260 2021-11-06T18:46:43 Z arujbansal Robot (JOI21_ho_t4) C++17
100 / 100
 968 ms 83776 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MXN = 1e5 + 1, MXM = 2e5 + 1;
const ll INF = 1e18 + 5;

struct state {
    int node, colour;
    ll cur_dist;

    state(int _node = 0, int _colour = 0, ll _cur_dist = 0) : node(_node), colour(_colour), cur_dist(_cur_dist) {}

    bool operator<(const state &other) const {
        return cur_dist > other.cur_dist;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    map<int, ll> sum[N];
    vector<array<int, 3>> g[N];
    map<int, vector<pair<int, int>>> edges[N];

    for (int i = 0; i < M; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--, b--;

        // {v, colour of edge, cost of deleting edge}
        g[a].emplace_back(array<int, 3>{b, c, p});
        g[b].emplace_back(array<int, 3>{a, c, p});

        // Sum of costs of all edges incident to a node with a particular colour
        sum[a][c] += p;
        sum[b][c] += p;

        // All edges incident to a node with a particular colour
        edges[a][c].emplace_back(b, p);
        edges[b][c].emplace_back(a, p);
    }

    vector<ll> dist(N, INF);
    dist[0] = 0;

    map<int, ll> dist_col[N];

    priority_queue<state> pq;
    pq.emplace(0, -1, 0); // -1 represents free will, no colour restriction

    while (!pq.empty()) {
        auto [u, colour, cur_dist] = pq.top();
        pq.pop();

        if (colour == -1) {
            if (dist[u] != cur_dist) continue;

            for (const auto &[v, edge_col, edge_cost] : g[u]) {
                // 2.1 and 2.2
                ll cost1 = min(cur_dist + sum[u][edge_col] - edge_cost, cur_dist + edge_cost);
                if (cost1 < dist[v]) {
                    dist[v] = cost1;
                    pq.emplace(v, -1, dist[v]);
                }

                // 2.3
                if (!dist_col[v].count(edge_col) || cur_dist < dist_col[v][edge_col]) {
                    dist_col[v][edge_col] = cur_dist;
                    pq.emplace(v, edge_col, cur_dist);
                }
            }
        } else {
            if (cur_dist != dist_col[u][colour]) continue;

            for (const auto &[v, edge_cost] : edges[u][colour]) {
                ll cost = cur_dist + sum[u][colour] - edge_cost;
                if (cost < dist[v]) {
                    dist[v] = cost;
                    pq.emplace(v, -1, cost);
                }
            }
        }
    }

    cout << (dist[N - 1] < INF ? dist[N - 1] : -1);
}

/*
    Observations:
    1. Always possible to change the colour of an edge so that it is different from all other edges connecting u if the answer is not -1 (?)
    2. Three cases if current edge E(u, v) is of colour C:
        2.1: We use E by changing colours of all other edges with C to go to v. At v, it's okay to use an edge of colour C since it gives us a worse cost than 2.2.
        2.2: We change E's colour and go to v. Don't change the colour of any other edge incident to u with colour C. We can use an edge of any colour from v.
             This gives us a worse cost if we use an edge of colour C form v because we double count the cost for this edge. Case 2.3 handles this.
        2.3: We change E's colour and use an edge of colour C from v.
*/

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 3 ms 1012 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 2 ms 844 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 24476 KB Output is correct
2 Correct 61 ms 13248 KB Output is correct
3 Correct 178 ms 19560 KB Output is correct
4 Correct 106 ms 17876 KB Output is correct
5 Correct 947 ms 83224 KB Output is correct
6 Correct 732 ms 72196 KB Output is correct
7 Correct 296 ms 51164 KB Output is correct
8 Correct 381 ms 52744 KB Output is correct
9 Correct 446 ms 52612 KB Output is correct
10 Correct 284 ms 42804 KB Output is correct
11 Correct 145 ms 32572 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 3 ms 1012 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 2 ms 844 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 716 KB Output is correct
21 Correct 175 ms 24476 KB Output is correct
22 Correct 61 ms 13248 KB Output is correct
23 Correct 178 ms 19560 KB Output is correct
24 Correct 106 ms 17876 KB Output is correct
25 Correct 947 ms 83224 KB Output is correct
26 Correct 732 ms 72196 KB Output is correct
27 Correct 296 ms 51164 KB Output is correct
28 Correct 381 ms 52744 KB Output is correct
29 Correct 446 ms 52612 KB Output is correct
30 Correct 284 ms 42804 KB Output is correct
31 Correct 145 ms 32572 KB Output is correct
32 Correct 113 ms 12188 KB Output is correct
33 Correct 148 ms 17404 KB Output is correct
34 Correct 432 ms 41652 KB Output is correct
35 Correct 262 ms 33356 KB Output is correct
36 Correct 280 ms 46084 KB Output is correct
37 Correct 300 ms 48572 KB Output is correct
38 Correct 284 ms 55096 KB Output is correct
39 Correct 148 ms 16936 KB Output is correct
40 Correct 403 ms 52528 KB Output is correct
41 Correct 418 ms 52616 KB Output is correct
42 Correct 472 ms 61108 KB Output is correct
43 Correct 228 ms 25904 KB Output is correct
44 Correct 347 ms 28348 KB Output is correct
45 Correct 336 ms 49068 KB Output is correct
46 Correct 279 ms 49008 KB Output is correct
47 Correct 311 ms 47792 KB Output is correct
48 Correct 968 ms 83776 KB Output is correct