oj.uz

Submission #531967

# Submission time Handle Problem Language Result Execution time Memory
531967 2022-03-02T01:58:58 Z Netr Robot (JOI21_ho_t4) C++14
100 / 100
 853 ms 85428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
typedef tuple<ll,ll,ll> ti;
 
#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif
 
const ll MAXN = 1e5 + 5;
const ll MAXM = 2e5 + 5;
const ll INF = 1ll<<60;
 
ll N,M,V[MAXN],D[MAXN];
map<ll, vector<pi>> edges[MAXN];
map<ll, ll> cc[MAXN], dp[MAXN];

void djikstras(ll src){
    fill(begin(D), end(D), INF);
    priority_queue<ti, vector<ti>, greater<ti>> pq;
    pq.push({D[src] = 0, src, 0});

    while(!pq.empty()){
        ll cdist, node, col;
        tie(cdist, node, col) = pq.top(); pq.pop();


        // if we're entering this node on an edge that was recoloured WITH the intention to leave this node on an edge with the ORIGINAL colour of the recoloured edge
        // we do this to avoid double counting the cost of recolouring the first edge
        if(col){
            if(dp[node][col] != cdist) continue;
            for(auto e : edges[node][col]){

                // outgoing edge uses the ORIGINAL colour and we include the cost of recolouring the previous edge
                ll cost = cc[node][col] - e.second + cdist;
                if(D[e.first] > cost){
                    pq.push({D[e.first] = cost, e.first, 0});
                }
            }
        }else{
            // standard entry to a node, available options are:
            // 1) recolour all same-coloured edges
            // 2) recolour edge to the "free" colour (existence proven by PHP), no intention to use the original colour in the next node (we don't need to do anything special, if it's double counted that's ok - best solution will come from option 3)
            // 3) recolour edge to the "free" colour, intending to use the original colour in the next node
            
            if(D[node] != cdist) continue;
            for(auto &c : edges[node]){
                for(auto e : c.second){

                    // Option 1
                    ll c1 = cc[node][c.first] - e.second + cdist;
                    if(D[e.first] > c1){
                        pq.push({D[e.first] = c1, e.first, 0});
                    }

                    // Option 2 (include price of recolouring)
                    ll c2 = e.second + cdist;
                    if(D[e.first] > c2){
                        pq.push({D[e.first] = c2, e.first, 0});
                    }

                    // Option 3 (don't include price of recolouring)
                    ll c3 = cdist;
                    if(!dp[e.first].count(c.first) || dp[e.first][c.first] > c3){
                        pq.push({dp[e.first][c.first] = c3, e.first, c.first});
                    }
                }
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        ll ai, bi, ci, pi;
        cin >> ai >> bi >> ci >> pi;
        edges[ai][ci].push_back({bi, pi});
        edges[bi][ci].push_back({ai, pi});
        cc[ai][ci] += pi;
        cc[bi][ci] += pi;
    }
    djikstras(1);
    cout << (D[N] == INF ? -1 : D[N]) << "\n";
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15180 KB Output is correct
2 Correct 8 ms 15180 KB Output is correct
3 Correct 7 ms 15200 KB Output is correct
4 Correct 8 ms 15180 KB Output is correct
5 Correct 10 ms 15228 KB Output is correct
6 Correct 8 ms 15180 KB Output is correct
7 Correct 8 ms 15368 KB Output is correct
8 Correct 8 ms 15232 KB Output is correct
9 Correct 11 ms 15820 KB Output is correct
10 Correct 11 ms 15640 KB Output is correct
11 Correct 9 ms 15564 KB Output is correct
12 Correct 9 ms 15436 KB Output is correct
13 Correct 8 ms 15564 KB Output is correct
14 Correct 8 ms 15564 KB Output is correct
15 Correct 8 ms 15436 KB Output is correct
16 Correct 11 ms 15564 KB Output is correct
17 Correct 12 ms 15564 KB Output is correct
18 Correct 8 ms 15264 KB Output is correct
19 Correct 10 ms 15436 KB Output is correct
20 Correct 9 ms 15440 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 33932 KB Output is correct
2 Correct 68 ms 24808 KB Output is correct
3 Correct 174 ms 30108 KB Output is correct
4 Correct 102 ms 27568 KB Output is correct
5 Correct 827 ms 79556 KB Output is correct
6 Correct 687 ms 68932 KB Output is correct
7 Correct 313 ms 56464 KB Output is correct
8 Correct 358 ms 46828 KB Output is correct
9 Correct 389 ms 50896 KB Output is correct
10 Correct 288 ms 48628 KB Output is correct
11 Correct 122 ms 33048 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15180 KB Output is correct
2 Correct 8 ms 15180 KB Output is correct
3 Correct 7 ms 15200 KB Output is correct
4 Correct 8 ms 15180 KB Output is correct
5 Correct 10 ms 15228 KB Output is correct
6 Correct 8 ms 15180 KB Output is correct
7 Correct 8 ms 15368 KB Output is correct
8 Correct 8 ms 15232 KB Output is correct
9 Correct 11 ms 15820 KB Output is correct
10 Correct 11 ms 15640 KB Output is correct
11 Correct 9 ms 15564 KB Output is correct
12 Correct 9 ms 15436 KB Output is correct
13 Correct 8 ms 15564 KB Output is correct
14 Correct 8 ms 15564 KB Output is correct
15 Correct 8 ms 15436 KB Output is correct
16 Correct 11 ms 15564 KB Output is correct
17 Correct 12 ms 15564 KB Output is correct
18 Correct 8 ms 15264 KB Output is correct
19 Correct 10 ms 15436 KB Output is correct
20 Correct 9 ms 15440 KB Output is correct
21 Correct 169 ms 33932 KB Output is correct
22 Correct 68 ms 24808 KB Output is correct
23 Correct 174 ms 30108 KB Output is correct
24 Correct 102 ms 27568 KB Output is correct
25 Correct 827 ms 79556 KB Output is correct
26 Correct 687 ms 68932 KB Output is correct
27 Correct 313 ms 56464 KB Output is correct
28 Correct 358 ms 46828 KB Output is correct
29 Correct 389 ms 50896 KB Output is correct
30 Correct 288 ms 48628 KB Output is correct
31 Correct 122 ms 33048 KB Output is correct
32 Correct 116 ms 29292 KB Output is correct
33 Correct 145 ms 30876 KB Output is correct
34 Correct 347 ms 51320 KB Output is correct
35 Correct 279 ms 42588 KB Output is correct
36 Correct 278 ms 47672 KB Output is correct
37 Correct 330 ms 50212 KB Output is correct
38 Correct 308 ms 59676 KB Output is correct
39 Correct 131 ms 33048 KB Output is correct
40 Correct 391 ms 52124 KB Output is correct
41 Correct 416 ms 52476 KB Output is correct
42 Correct 437 ms 61672 KB Output is correct
43 Correct 191 ms 37768 KB Output is correct
44 Correct 372 ms 43740 KB Output is correct
45 Correct 281 ms 47504 KB Output is correct
46 Correct 237 ms 47848 KB Output is correct
47 Correct 279 ms 50260 KB Output is correct
48 Correct 853 ms 85428 KB Output is correct