oj.uz

Submission #875195

# Submission time Handle Problem Language Result Execution time Memory
875195 2023-11-18T18:53:10 Z trytovoi Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 233 ms 28464 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T> bool ckmin(T& x, const T& y) { return x > y ? x = y, 1 : 0; }
template<typename T> bool ckmax(T& x, const T& y) { return x < y ? x = y, 1 : 0; }

const long long INF = (long long) 1e18;
const int MAX_NODE = (int) 1e5 + 5;
const int MAX_EDGE = (int) 2e5 + 5;

int n, m;
int S, T, U, V;
vector<pair<int, int>> adj[MAX_NODE];

struct Data {
    int u;
    long long w;
    
    Data(int _u = 0, long long _w = 0) {
        u = _u; w = _w;
    }
    
    bool operator < (const Data& other) const {
        return w > other.w;
    }
};

void dijkstra(int s, vector<long long>& dist) {
    priority_queue<Data> Q;
    Q.push(Data(s, dist[s] = 0));
    while (!Q.empty()) {
        auto [u, du] = Q.top(); Q.pop();
        if (du != dist[u]) continue;
        
        for (auto [v, dv] : adj[u]) {
            long long cost = du + dv;
            if (ckmin(dist[v], cost)) Q.push(Data(v, dist[v]));
        }
    }
}

namespace SUBTASK_1 {
    
    void solve(void) {
        vector<long long> distSU(n + 1, INF);
        dijkstra(S, distSU);
        vector<long long> distT(n + 1, INF);
        dijkstra(T, distT);
        vector<long long> distV(n + 1, INF);
        dijkstra(V, distV);
        
        long long ans = distV[U];
        for (int i = 1; i <= n; ++i) if (distSU[i] + distT[i] == distSU[T]) ckmin(ans, distV[i]);
        cout << ans << '\n';
    }
    
}

namespace SUBTASK_3 {
    
    const int MX = 303;
    
    long long dist[MX][MX];
    
    void solve(void) {
        memset(dist, 0x3f, sizeof dist);
        for (int i = 1; i <= n; ++i) {
            dist[i][i] = 0;
            for (auto [v, w] : adj[i]) dist[i][v] = dist[v][i] = w;
        }
        
        for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
            ckmin(dist[i][j], dist[i][k] + dist[k][j]);
        
        long long ans = dist[U][V];
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) 
            if (dist[S][i] + dist[i][j] + dist[j][T] == dist[S][T]) ckmin(ans, min(dist[V][i] + dist[j][U], dist[U][i] + dist[j][V]));
        cout << ans << '\n';
    }
    
}

namespace FULL {

vector<int> tree[MAX_NODE];

void solve(void) {
    vector<long long> distS(n + 1, INF), distT(n + 1, INF), distU(n + 1, INF), distV(n + 1, INF);
    dijkstra(S, distS); dijkstra(T, distT); dijkstra(U, distU); dijkstra(V, distV);
    for (int u = 1; u <= n; ++u) for (auto [v, w] : adj[u]) {
        if (distS[u] + w + distT[v] == distS[T]) tree[u].push_back(v);
    }
    long long ans = distU[V];
    vector<vector<long long>> dp(n + 1, vector<long long>(2, INF));
    vector<bool> vis(n + 1, false);
    function<void(int)> dfs = [&](int u) {
        vis[u] = true;
        for (int v : tree[u]) {
            if (!vis[v]) dfs(v);
            ckmin(dp[u][0], min(dp[v][0], distU[v]));
            ckmin(dp[u][1], min(dp[v][1], distV[v]));
        }
        if (dp[u][0] < INF) ckmin(ans, dp[u][0] + distV[u]);
        if (dp[u][1] < INF) ckmin(ans, dp[u][1] + distU[u]);
    }; 
    dfs(S);
    cout << ans << '\n';
}
    
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    if (S == U) {
        SUBTASK_1::solve();
        return 0;
    }
    if (n <= 300) {
        SUBTASK_3::solve();
        return 0;
    }
    FULL::solve();
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         auto [u, du] = Q.top(); Q.pop();
      |              ^
commuter_pass.cpp:35:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         for (auto [v, dv] : adj[u]) {
      |                   ^
commuter_pass.cpp: In function 'void SUBTASK_3::solve()':
commuter_pass.cpp:69:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |             for (auto [v, w] : adj[i]) dist[i][v] = dist[v][i] = w;
      |                       ^
commuter_pass.cpp: In function 'void FULL::solve()':
commuter_pass.cpp:90:44: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |     for (int u = 1; u <= n; ++u) for (auto [v, w] : adj[u]) {
      |                                            ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 17664 KB Output is correct
2 Correct 167 ms 16184 KB Output is correct
3 Correct 129 ms 16628 KB Output is correct
4 Correct 122 ms 17364 KB Output is correct
5 Correct 144 ms 16180 KB Output is correct
6 Correct 149 ms 17452 KB Output is correct
7 Correct 129 ms 16176 KB Output is correct
8 Correct 139 ms 16164 KB Output is correct
9 Correct 142 ms 16204 KB Output is correct
10 Correct 100 ms 15944 KB Output is correct
11 Correct 49 ms 11344 KB Output is correct
12 Correct 144 ms 16148 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 23580 KB Output is correct
2 Correct 209 ms 24016 KB Output is correct
3 Correct 215 ms 23672 KB Output is correct
4 Correct 209 ms 24008 KB Output is correct
5 Correct 185 ms 24808 KB Output is correct
6 Correct 203 ms 27556 KB Output is correct
7 Correct 210 ms 28464 KB Output is correct
8 Correct 233 ms 24024 KB Output is correct
9 Correct 185 ms 24732 KB Output is correct
10 Correct 226 ms 23516 KB Output is correct
11 Correct 74 ms 25428 KB Output is correct
12 Correct 210 ms 28416 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6488 KB Output is correct
2 Correct 22 ms 5724 KB Output is correct
3 Correct 22 ms 5884 KB Output is correct
4 Correct 27 ms 7000 KB Output is correct
5 Correct 25 ms 6488 KB Output is correct
6 Correct 23 ms 5920 KB Output is correct
7 Correct 24 ms 5956 KB Output is correct
8 Correct 26 ms 5920 KB Output is correct
9 Correct 24 ms 5720 KB Output is correct
10 Correct 26 ms 6492 KB Output is correct
11 Correct 21 ms 5724 KB Output is correct
12 Correct 22 ms 5724 KB Output is correct
13 Correct 21 ms 5724 KB Output is correct
14 Correct 23 ms 5904 KB Output is correct
15 Correct 23 ms 5724 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 17664 KB Output is correct
2 Correct 167 ms 16184 KB Output is correct
3 Correct 129 ms 16628 KB Output is correct
4 Correct 122 ms 17364 KB Output is correct
5 Correct 144 ms 16180 KB Output is correct
6 Correct 149 ms 17452 KB Output is correct
7 Correct 129 ms 16176 KB Output is correct
8 Correct 139 ms 16164 KB Output is correct
9 Correct 142 ms 16204 KB Output is correct
10 Correct 100 ms 15944 KB Output is correct
11 Correct 49 ms 11344 KB Output is correct
12 Correct 144 ms 16148 KB Output is correct
13 Correct 179 ms 23580 KB Output is correct
14 Correct 209 ms 24016 KB Output is correct
15 Correct 215 ms 23672 KB Output is correct
16 Correct 209 ms 24008 KB Output is correct
17 Correct 185 ms 24808 KB Output is correct
18 Correct 203 ms 27556 KB Output is correct
19 Correct 210 ms 28464 KB Output is correct
20 Correct 233 ms 24024 KB Output is correct
21 Correct 185 ms 24732 KB Output is correct
22 Correct 226 ms 23516 KB Output is correct
23 Correct 74 ms 25428 KB Output is correct
24 Correct 210 ms 28416 KB Output is correct
25 Correct 25 ms 6488 KB Output is correct
26 Correct 22 ms 5724 KB Output is correct
27 Correct 22 ms 5884 KB Output is correct
28 Correct 27 ms 7000 KB Output is correct
29 Correct 25 ms 6488 KB Output is correct
30 Correct 23 ms 5920 KB Output is correct
31 Correct 24 ms 5956 KB Output is correct
32 Correct 26 ms 5920 KB Output is correct
33 Correct 24 ms 5720 KB Output is correct
34 Correct 26 ms 6492 KB Output is correct
35 Correct 21 ms 5724 KB Output is correct
36 Correct 22 ms 5724 KB Output is correct
37 Correct 21 ms 5724 KB Output is correct
38 Correct 23 ms 5904 KB Output is correct
39 Correct 23 ms 5724 KB Output is correct
40 Correct 192 ms 19812 KB Output is correct
41 Correct 149 ms 20096 KB Output is correct
42 Correct 150 ms 20200 KB Output is correct
43 Correct 96 ms 25256 KB Output is correct
44 Correct 78 ms 25428 KB Output is correct
45 Correct 161 ms 23436 KB Output is correct
46 Correct 186 ms 23336 KB Output is correct
47 Correct 172 ms 23952 KB Output is correct
48 Correct 90 ms 23888 KB Output is correct
49 Correct 145 ms 23636 KB Output is correct
50 Correct 155 ms 26160 KB Output is correct
51 Correct 165 ms 26804 KB Output is correct