oj.uz

Submission #503060

# Submission time Handle Problem Language Result Execution time Memory
503060 2022-01-07T04:43:01 Z XII Robot (JOI21_ho_t4) C++17
100 / 100
 783 ms 81860 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "JOI21_ho_t4"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 1e5 + 1;
const ll INF = 1e18;
int n, m;
using pi = pair<int, int>;
map<int, vector<pi>> adj[N];
map<int, ll> tot[N], dp2[N];
ll dp[N];

using T = pair<ll, pair<int, int>>;
struct cmp{
    const bool operator()(const T &a, const T &b) const {
        return a.fi > b.fi;
    }
};
priority_queue<T, vector<T>, cmp> pq;
//priority_queue<T, vector<T>, greater<T>> pq;

ll dijkstra(const int &s, const int &e){
    fill(dp + 1, dp + n + 1, INF);
    pq.emplace(0, mp(s, 0));
    dp[s] = 0;
    while(!pq.empty()){
        ll wu = pq.top().fi;
        auto [u, cu] = pq.top().se;
        pq.pop();
        if(cu){
            if(dp2[u][cu] != wu) continue;
            for(auto [v, wv]: adj[u][cu]){
                ll w = wu + (tot[u][cu] - wv);
                if(dp[v] > w){
                    dp[v] = w;
                    pq.emplace(dp[v], mp(v, 0));
                }
            }
        } else{
            if(dp[u] != wu) continue;
            for(auto [cv, ed]: adj[u]){
                for(auto [v, wv]: ed){
                    ll case1 = wu + wv;
                    if(dp[v] > case1){
                        dp[v] = case1;
                        pq.emplace(dp[v], mp(v, 0));
                    }
                    ll case2 = wu + (tot[u][cv] - wv);
                    if(dp[v] > case2){
                        dp[v] = case2;
                        pq.emplace(dp[v], mp(v, 0));
                    }
                    ll case3 = wu;
                    if(!dp2[v].count(cv) || dp2[v][cv] > case3){
                        dp2[v][cv] = case3;
                        pq.emplace(dp2[v][cv], mp(v, cv));
                    }
                }
            }
        }
    }
    return (dp[e] == INF ? -1 : dp[e]);
}

int main(){
    IOS;
    Fi();
    cin >> n >> m;
    FORU(i, 1, m){
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u][c].eb(v, p);
        adj[v][c].eb(u, p);
        tot[u][c] += p;
        tot[v][c] += p;
    }
    cout << dijkstra(1, n);
    return 0;
}

Compilation message

Main.cpp: In function 'void Fi()':
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14284 KB Output is correct
5 Correct 7 ms 14460 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14540 KB Output is correct
8 Correct 7 ms 14416 KB Output is correct
9 Correct 10 ms 15052 KB Output is correct
10 Correct 9 ms 14936 KB Output is correct
11 Correct 8 ms 14668 KB Output is correct
12 Correct 8 ms 14668 KB Output is correct
13 Correct 8 ms 14668 KB Output is correct
14 Correct 8 ms 14748 KB Output is correct
15 Correct 8 ms 14668 KB Output is correct
16 Correct 9 ms 14676 KB Output is correct
17 Correct 9 ms 14712 KB Output is correct
18 Correct 9 ms 14540 KB Output is correct
19 Correct 8 ms 14540 KB Output is correct
20 Correct 8 ms 14672 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 32684 KB Output is correct
2 Correct 77 ms 24016 KB Output is correct
3 Correct 158 ms 28696 KB Output is correct
4 Correct 100 ms 26680 KB Output is correct
5 Correct 742 ms 79664 KB Output is correct
6 Correct 573 ms 68268 KB Output is correct
7 Correct 264 ms 48128 KB Output is correct
8 Correct 320 ms 46624 KB Output is correct
9 Correct 318 ms 46472 KB Output is correct
10 Correct 286 ms 46104 KB Output is correct
11 Correct 119 ms 30800 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14284 KB Output is correct
5 Correct 7 ms 14460 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14540 KB Output is correct
8 Correct 7 ms 14416 KB Output is correct
9 Correct 10 ms 15052 KB Output is correct
10 Correct 9 ms 14936 KB Output is correct
11 Correct 8 ms 14668 KB Output is correct
12 Correct 8 ms 14668 KB Output is correct
13 Correct 8 ms 14668 KB Output is correct
14 Correct 8 ms 14748 KB Output is correct
15 Correct 8 ms 14668 KB Output is correct
16 Correct 9 ms 14676 KB Output is correct
17 Correct 9 ms 14712 KB Output is correct
18 Correct 9 ms 14540 KB Output is correct
19 Correct 8 ms 14540 KB Output is correct
20 Correct 8 ms 14672 KB Output is correct
21 Correct 170 ms 32684 KB Output is correct
22 Correct 77 ms 24016 KB Output is correct
23 Correct 158 ms 28696 KB Output is correct
24 Correct 100 ms 26680 KB Output is correct
25 Correct 742 ms 79664 KB Output is correct
26 Correct 573 ms 68268 KB Output is correct
27 Correct 264 ms 48128 KB Output is correct
28 Correct 320 ms 46624 KB Output is correct
29 Correct 318 ms 46472 KB Output is correct
30 Correct 286 ms 46104 KB Output is correct
31 Correct 119 ms 30800 KB Output is correct
32 Correct 109 ms 24380 KB Output is correct
33 Correct 126 ms 26820 KB Output is correct
34 Correct 366 ms 47484 KB Output is correct
35 Correct 266 ms 39008 KB Output is correct
36 Correct 256 ms 43016 KB Output is correct
37 Correct 308 ms 45024 KB Output is correct
38 Correct 268 ms 51760 KB Output is correct
39 Correct 163 ms 26888 KB Output is correct
40 Correct 318 ms 47832 KB Output is correct
41 Correct 361 ms 47964 KB Output is correct
42 Correct 456 ms 57624 KB Output is correct
43 Correct 226 ms 35144 KB Output is correct
44 Correct 393 ms 38512 KB Output is correct
45 Correct 297 ms 44596 KB Output is correct
46 Correct 239 ms 44632 KB Output is correct
47 Correct 288 ms 44772 KB Output is correct
48 Correct 783 ms 81860 KB Output is correct