oj.uz

Submission #658386

# Submission time Handle Problem Language Result Execution time Memory
658386 2022-11-13T04:29:17 Z TheEpicCowOfLife Robot (JOI21_ho_t4) C++14
100 / 100
 919 ms 91720 KB 
#include <bits/stdc++.h>

// #ifdef DEBUG
// #define D(..) = printf(..)
// #else
// #define D(..) = printf(..)
// #endif
using namespace std;

int n,m;
typedef long long ll;
typedef pair<ll, ll> pll;

// price, target
map<int,vector<pll>> g[100005];

map<int,ll> tc[100005];

/// final graph to dijkstra over
vector<pll> fg[100005];


// Observations: You want to reach each node at most once
// You can always assign a new unique edge 
// At each node you have two choices: Assign every other edge, and take the edge for free,
// or just assign

inline void add_edge(int u, int v, int c, long long p){
    if (g[u].find(c) == g[u].end()){
        vector<pll> vec;
        vec.push_back({p,v});
        g[u][c] = vec;
        tc[u][c] = p;
    }
    else{
        g[u][c].push_back({p,v});
        tc[u][c] += p;
    }
}
inline void add_change_edge(int u, int v, int c, long long p){
    // Add edge from u -> v
    fg[u].push_back({v,p});
    // printf("Added change base %d-%lld %lld\n", u, v, p);
    // I'm pretty sure you only need to consider the top 2 weights, but the math seems ab it tight and 
    // idk if I have all the cases considered

    // ll maxw = g[u][c][0].first;
    for (int i = 0; i < min(2,(int) g[v][c].size()); i++){
        ll tgt = g[v][c][i].second;
        ll w = g[v][c][i].first;
        if (tgt == u){
            continue; // don't do a back-edge
        }
        // New edge: Go from u to v to tgt, where we change u -> v, and don't change v -> tgt
        fg[u].push_back({tgt, tc[v][c] - w});

        // printf("Added change case %d-%lld %lld\n", u, tgt, tc[v][c] - w);
    }
}

ll dist[100005];
bool explored[100005];

priority_queue<pll,vector<pll>,greater<pll>> q;

int main(){
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++){
        int u,v,c;
        long long p;        
        scanf("%d %d %d %lld", &u,&v,&c,&p);
        add_edge(u,v,c,p);
        add_edge(v,u,c,p);
    }

    for (int i = 1; i <= n; i++){
        dist[i] = 1e18;
        // sort the vecs
        for (auto cur : g[i]){
            int c = cur.first;
            sort(g[i][c].begin(),g[i][c].end(), greater<pll>());
        }
    }

    for (int i = 1; i <= n; i++){
        for (auto cur : g[i]){
            int c = cur.first;            
            for (auto thing : cur.second){
                ll v = thing.second;
                ll p = thing.first;
                add_change_edge(i,v,c,p);
                fg[i].push_back({v,tc[i][c] - p});
                // printf("%lld %lld %lld\n", i, v , p);
            }
        }              
    }

    // for (int i = 1; i <= n; i++){
    //     for (auto tgt : fg[i]){
    //     }
    // }

    dist[1] = 1;
    q.push({0,1});
    while (!q.empty()){
        auto cur = q.top();
        q.pop();
        long long d = cur.first;
        long long x = cur.second;
        if (explored[x]){
            continue;
        }
        explored[x] = true;
        for (auto tgt : fg[x]){
            ll tdist = tgt.second + d;
            if (!explored[tgt.first] && tdist < dist[tgt.first]){
                q.push({tdist,tgt.first});
                dist[tgt.first] = tdist;
            }
        }       
    }
    if (dist[n] > 9e17){
        printf("-1\n");
    }
    else{
        printf("%lld\n", dist[n]);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d %d %d %lld", &u,&v,&c,&p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11964 KB Output is correct
7 Correct 7 ms 12244 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12788 KB Output is correct
10 Correct 9 ms 12628 KB Output is correct
11 Correct 7 ms 12580 KB Output is correct
12 Correct 7 ms 12500 KB Output is correct
13 Correct 7 ms 12556 KB Output is correct
14 Correct 7 ms 12500 KB Output is correct
15 Correct 6 ms 12372 KB Output is correct
16 Correct 7 ms 12628 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 6 ms 12244 KB Output is correct
19 Correct 8 ms 12628 KB Output is correct
20 Correct 7 ms 12500 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 37704 KB Output is correct
2 Correct 78 ms 24124 KB Output is correct
3 Correct 220 ms 48000 KB Output is correct
4 Correct 111 ms 29440 KB Output is correct
5 Correct 919 ms 86644 KB Output is correct
6 Correct 711 ms 78284 KB Output is correct
7 Correct 331 ms 63404 KB Output is correct
8 Correct 520 ms 69836 KB Output is correct
9 Correct 523 ms 70008 KB Output is correct
10 Correct 381 ms 53804 KB Output is correct
11 Correct 216 ms 42564 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11964 KB Output is correct
7 Correct 7 ms 12244 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12788 KB Output is correct
10 Correct 9 ms 12628 KB Output is correct
11 Correct 7 ms 12580 KB Output is correct
12 Correct 7 ms 12500 KB Output is correct
13 Correct 7 ms 12556 KB Output is correct
14 Correct 7 ms 12500 KB Output is correct
15 Correct 6 ms 12372 KB Output is correct
16 Correct 7 ms 12628 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 6 ms 12244 KB Output is correct
19 Correct 8 ms 12628 KB Output is correct
20 Correct 7 ms 12500 KB Output is correct
21 Correct 182 ms 37704 KB Output is correct
22 Correct 78 ms 24124 KB Output is correct
23 Correct 220 ms 48000 KB Output is correct
24 Correct 111 ms 29440 KB Output is correct
25 Correct 919 ms 86644 KB Output is correct
26 Correct 711 ms 78284 KB Output is correct
27 Correct 331 ms 63404 KB Output is correct
28 Correct 520 ms 69836 KB Output is correct
29 Correct 523 ms 70008 KB Output is correct
30 Correct 381 ms 53804 KB Output is correct
31 Correct 216 ms 42564 KB Output is correct
32 Correct 156 ms 43336 KB Output is correct
33 Correct 194 ms 42156 KB Output is correct
34 Correct 380 ms 57672 KB Output is correct
35 Correct 281 ms 48032 KB Output is correct
36 Correct 301 ms 52392 KB Output is correct
37 Correct 330 ms 58764 KB Output is correct
38 Correct 313 ms 63396 KB Output is correct
39 Correct 193 ms 56352 KB Output is correct
40 Correct 529 ms 70548 KB Output is correct
41 Correct 542 ms 70628 KB Output is correct
42 Correct 536 ms 71692 KB Output is correct
43 Correct 240 ms 42728 KB Output is correct
44 Correct 450 ms 68116 KB Output is correct
45 Correct 424 ms 58364 KB Output is correct
46 Correct 420 ms 58084 KB Output is correct
47 Correct 320 ms 57328 KB Output is correct
48 Correct 917 ms 91720 KB Output is correct