oj.uz

Submission #677477

# Submission time Handle Problem Language Result Execution time Memory
677477 2023-01-03T12:23:21 Z chiferr Robot (JOI21_ho_t4) C++14
100 / 100
 971 ms 96912 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(4,(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 6 ms 12004 KB Output is correct
3 Correct 6 ms 12056 KB Output is correct
4 Correct 6 ms 12052 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 8 ms 11956 KB Output is correct
7 Correct 8 ms 12272 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 10 ms 12788 KB Output is correct
10 Correct 10 ms 12700 KB Output is correct
11 Correct 8 ms 12628 KB Output is correct
12 Correct 10 ms 12568 KB Output is correct
13 Correct 9 ms 12704 KB Output is correct
14 Correct 9 ms 12700 KB Output is correct
15 Correct 8 ms 12440 KB Output is correct
16 Correct 9 ms 12704 KB Output is correct
17 Correct 8 ms 12628 KB Output is correct
18 Correct 7 ms 12244 KB Output is correct
19 Correct 10 ms 12704 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 219 ms 41868 KB Output is correct
2 Correct 73 ms 25400 KB Output is correct
3 Correct 274 ms 60816 KB Output is correct
4 Correct 118 ms 31944 KB Output is correct
5 Correct 936 ms 90276 KB Output is correct
6 Correct 797 ms 86208 KB Output is correct
7 Correct 348 ms 79952 KB Output is correct
8 Correct 579 ms 86204 KB Output is correct
9 Correct 562 ms 86196 KB Output is correct
10 Correct 389 ms 58456 KB Output is correct
11 Correct 245 ms 47972 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 6 ms 12004 KB Output is correct
3 Correct 6 ms 12056 KB Output is correct
4 Correct 6 ms 12052 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 8 ms 11956 KB Output is correct
7 Correct 8 ms 12272 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 10 ms 12788 KB Output is correct
10 Correct 10 ms 12700 KB Output is correct
11 Correct 8 ms 12628 KB Output is correct
12 Correct 10 ms 12568 KB Output is correct
13 Correct 9 ms 12704 KB Output is correct
14 Correct 9 ms 12700 KB Output is correct
15 Correct 8 ms 12440 KB Output is correct
16 Correct 9 ms 12704 KB Output is correct
17 Correct 8 ms 12628 KB Output is correct
18 Correct 7 ms 12244 KB Output is correct
19 Correct 10 ms 12704 KB Output is correct
20 Correct 7 ms 12500 KB Output is correct
21 Correct 219 ms 41868 KB Output is correct
22 Correct 73 ms 25400 KB Output is correct
23 Correct 274 ms 60816 KB Output is correct
24 Correct 118 ms 31944 KB Output is correct
25 Correct 936 ms 90276 KB Output is correct
26 Correct 797 ms 86208 KB Output is correct
27 Correct 348 ms 79952 KB Output is correct
28 Correct 579 ms 86204 KB Output is correct
29 Correct 562 ms 86196 KB Output is correct
30 Correct 389 ms 58456 KB Output is correct
31 Correct 245 ms 47972 KB Output is correct
32 Correct 239 ms 62364 KB Output is correct
33 Correct 222 ms 54720 KB Output is correct
34 Correct 440 ms 66320 KB Output is correct
35 Correct 336 ms 56972 KB Output is correct
36 Correct 315 ms 61612 KB Output is correct
37 Correct 349 ms 74548 KB Output is correct
38 Correct 335 ms 79732 KB Output is correct
39 Correct 244 ms 75128 KB Output is correct
40 Correct 586 ms 87556 KB Output is correct
41 Correct 579 ms 87488 KB Output is correct
42 Correct 574 ms 81356 KB Output is correct
43 Correct 302 ms 48772 KB Output is correct
44 Correct 496 ms 82536 KB Output is correct
45 Correct 439 ms 68696 KB Output is correct
46 Correct 366 ms 61756 KB Output is correct
47 Correct 371 ms 73164 KB Output is correct
48 Correct 971 ms 96912 KB Output is correct