oj.uz

Submission #476848

# Submission time Handle Problem Language Result Execution time Memory
476848 2021-09-28T16:24:41 Z tranxuanbach Robot (JOI21_ho_t4) C++17
100 / 100
 987 ms 109780 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e5 + 5, M = 2e5 + 5;

struct Edge{
    int u, v, c, p;

    Edge(){

    }

    Edge(int u, int v, int c, int p): u(u), v(v), c(c), p(p){

    }
};

int n, m;
Edge edges[2 * M];
vi adj[N];

unordered_map <int, vi> mppc[N];
unordered_map <int, ll> mppsp[N];

unordered_map <int, ll> distc[N];
ll dist[N];
priority_queue <tuple <ll, int, int>, vector <tuple <ll, int, int>>, greater <tuple <ll, int, int>>> pq;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m;
    ForE(i, 1, m){
        int u, v, c, p; cin >> u >> v >> c >> p;
        edges[2 * i - 1] = Edge(u, v, c, p);
        edges[2 * i] = Edge(v, u, c, p);
        adj[u].emplace_back(2 * i - 1);
        adj[v].emplace_back(2 * i);
    }

    memset(dist, 0x3f, sizeof(dist));
    ForE(i, 1, 2 * m){
        mppc[edges[i].u][edges[i].c].emplace_back(i);
        mppsp[edges[i].u][edges[i].c] += edges[i].p;
        distc[edges[i].u][edges[i].c] = dist[0];
    }
    dist[1] = 0; pq.emplace(dist[1], 1, 0);
    while (!pq.empty()){
        ll d; int u, c; tie(d, u, c) = pq.top(); pq.pop();
        if (!c){
            if (d != dist[u]){
                continue;
            }
            Fora(elem, mppc[u]){
                if (isz(elem.se) == 1){
                    int i = elem.se[0];
                    if (dist[edges[i].v] > d){
                        dist[edges[i].v] = d;
                        pq.emplace(dist[edges[i].v], edges[i].v, 0);
                    }
                }
                Fora(i, elem.se){
                    if (dist[edges[i].v] > d + edges[i].p){
                        dist[edges[i].v] = d + edges[i].p;
                        pq.emplace(dist[edges[i].v], edges[i].v, 0);
                    }
                    if (distc[edges[i].v][edges[i].c] > d){
                        distc[edges[i].v][edges[i].c] = d;
                        pq.emplace(d, edges[i].v, edges[i].c);
                    }
                }
                if (distc[u][elem.fi] > d){
                    distc[u][elem.fi] = d;
                    pq.emplace(d, u, elem.fi);
                }
            }
        }
        else{
            if (d != distc[u][c]){
                continue;
            }
            if (isz(mppc[u][c]) == 1){
                continue;
            }
            Fora(i, mppc[u][c]){
                if (dist[edges[i].v] > distc[u][c] + mppsp[u][c] - edges[i].p){
                    dist[edges[i].v] = distc[u][c] + mppsp[u][c] - edges[i].p;
                    pq.emplace(dist[edges[i].v], edges[i].v, 0);
                }
            }
        }
    }
    cout << (dist[n] == dist[0] ? -1 : dist[n]) << endl;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19788 KB Output is correct
2 Correct 11 ms 19888 KB Output is correct
3 Correct 11 ms 19788 KB Output is correct
4 Correct 13 ms 19888 KB Output is correct
5 Correct 11 ms 19884 KB Output is correct
6 Correct 10 ms 19888 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 12 ms 19916 KB Output is correct
9 Correct 14 ms 20716 KB Output is correct
10 Correct 15 ms 20720 KB Output is correct
11 Correct 14 ms 20568 KB Output is correct
12 Correct 13 ms 20412 KB Output is correct
13 Correct 14 ms 20612 KB Output is correct
14 Correct 14 ms 20616 KB Output is correct
15 Correct 14 ms 20408 KB Output is correct
16 Correct 13 ms 20428 KB Output is correct
17 Correct 13 ms 20428 KB Output is correct
18 Correct 13 ms 20300 KB Output is correct
19 Correct 12 ms 20156 KB Output is correct
20 Correct 14 ms 20428 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 43080 KB Output is correct
2 Correct 121 ms 32452 KB Output is correct
3 Correct 336 ms 39600 KB Output is correct
4 Correct 195 ms 37952 KB Output is correct
5 Correct 966 ms 109780 KB Output is correct
6 Correct 872 ms 97580 KB Output is correct
7 Correct 537 ms 83464 KB Output is correct
8 Correct 574 ms 78868 KB Output is correct
9 Correct 675 ms 78816 KB Output is correct
10 Correct 467 ms 62836 KB Output is correct
11 Correct 246 ms 61764 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19788 KB Output is correct
2 Correct 11 ms 19888 KB Output is correct
3 Correct 11 ms 19788 KB Output is correct
4 Correct 13 ms 19888 KB Output is correct
5 Correct 11 ms 19884 KB Output is correct
6 Correct 10 ms 19888 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 12 ms 19916 KB Output is correct
9 Correct 14 ms 20716 KB Output is correct
10 Correct 15 ms 20720 KB Output is correct
11 Correct 14 ms 20568 KB Output is correct
12 Correct 13 ms 20412 KB Output is correct
13 Correct 14 ms 20612 KB Output is correct
14 Correct 14 ms 20616 KB Output is correct
15 Correct 14 ms 20408 KB Output is correct
16 Correct 13 ms 20428 KB Output is correct
17 Correct 13 ms 20428 KB Output is correct
18 Correct 13 ms 20300 KB Output is correct
19 Correct 12 ms 20156 KB Output is correct
20 Correct 14 ms 20428 KB Output is correct
21 Correct 301 ms 43080 KB Output is correct
22 Correct 121 ms 32452 KB Output is correct
23 Correct 336 ms 39600 KB Output is correct
24 Correct 195 ms 37952 KB Output is correct
25 Correct 966 ms 109780 KB Output is correct
26 Correct 872 ms 97580 KB Output is correct
27 Correct 537 ms 83464 KB Output is correct
28 Correct 574 ms 78868 KB Output is correct
29 Correct 675 ms 78816 KB Output is correct
30 Correct 467 ms 62836 KB Output is correct
31 Correct 246 ms 61764 KB Output is correct
32 Correct 174 ms 31124 KB Output is correct
33 Correct 259 ms 38844 KB Output is correct
34 Correct 544 ms 58732 KB Output is correct
35 Correct 441 ms 53176 KB Output is correct
36 Correct 449 ms 75692 KB Output is correct
37 Correct 589 ms 78968 KB Output is correct
38 Correct 523 ms 86736 KB Output is correct
39 Correct 226 ms 36532 KB Output is correct
40 Correct 581 ms 78232 KB Output is correct
41 Correct 639 ms 78404 KB Output is correct
42 Correct 726 ms 83736 KB Output is correct
43 Correct 301 ms 44092 KB Output is correct
44 Correct 490 ms 44072 KB Output is correct
45 Correct 542 ms 75468 KB Output is correct
46 Correct 457 ms 74420 KB Output is correct
47 Correct 504 ms 77992 KB Output is correct
48 Correct 987 ms 109260 KB Output is correct