oj.uz

Submission #928602

# Submission time Handle Problem Language Result Execution time Memory
928602 2024-02-16T18:04:18 Z AlphaMale06 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 282 ms 29192 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define F first
#define S second

const int N = 1e5+5;
const int inf = 1e16;

vector<pair<int, int>> adj[N];
int dist[N][4];
bool mark[N];
int dp[N][2];
int sp;
int ans;
vector<int> dag[N];
int indeg[N];
int hv[N];

void dijkstra(int s, int t){
    for(int i=0; i< N; i++){
        mark[i]=0;
        dist[i][t]=inf;
    }
    dist[s][t]=0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while(pq.size()){
        auto p = pq.top();
        pq.pop();
        if(mark[p.S] || dist[p.S][t]<p.F)continue;
        mark[p.S]=1;
        for(auto to : adj[p.S]){
            if(!mark[to.F] && to.S+dist[p.S][t]<dist[to.F][t]){
                dist[to.F][t]=to.S+dist[p.S][t];
                pq.push({dist[to.F][t], to.F});
            }
        }
    }
}

void calcdp(int s){
    for(int i=0; i<N; i++){
        dp[i][0]=dp[i][1]=inf;
        hv[i]=0;
    }
    queue<int> q;
    dp[s][0]=dist[s][2];
    dp[s][1]=dist[s][3];
    q.push(s);
    while(q.size()){
        int v = q.front();
        q.pop();
        ans=min({ans, dp[v][0]+dist[v][3], dp[v][1]+dist[v][2]});
        for(int to : dag[v]){
            dp[to][0]=min(dp[v][0], dist[to][2]);
            dp[to][1]=min(dp[v][1], dist[to][3]);
            hv[to]++;
            if(hv[to]==indeg[to])q.push(to);
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for(int i=0; i< m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    dijkstra(s, 0);
    dijkstra(t, 1);
    dijkstra(u, 2);
    dijkstra(v, 3);
    sp=dist[s][1];
    ans=dist[v][2];
    dp[0][0]=inf;
    dp[0][1]=inf;
    for(int i=1; i<=n; i++){
        for(auto to : adj[i]){
            if(dist[i][0]+dist[to.F][1]+to.S==sp){
                dag[i].pb(to.F);
                indeg[to.F]++;
            }
        }
    }
    calcdp(s);
    for(int i=1; i<=n; i++){
        indeg[i]=0;
        dag[i].clear();
    }
    for(int i=1; i<=n; i++){
        for(auto to : adj[i]){
            if(dist[i][1]+dist[to.F][0]+to.S==sp){
                dag[i].pb(to.F);
                indeg[to.F]++;
            }
        }
    }
    calcdp(t);
    cout << ans << '\n';
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 25108 KB Output is correct
2 Correct 257 ms 23596 KB Output is correct
3 Correct 260 ms 28384 KB Output is correct
4 Correct 230 ms 28540 KB Output is correct
5 Correct 258 ms 26900 KB Output is correct
6 Correct 236 ms 28688 KB Output is correct
7 Correct 249 ms 27436 KB Output is correct
8 Correct 234 ms 26896 KB Output is correct
9 Correct 222 ms 27848 KB Output is correct
10 Correct 168 ms 27708 KB Output is correct
11 Correct 74 ms 19540 KB Output is correct
12 Correct 215 ms 27744 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 23688 KB Output is correct
2 Correct 232 ms 23624 KB Output is correct
3 Correct 239 ms 23476 KB Output is correct
4 Correct 230 ms 23608 KB Output is correct
5 Correct 250 ms 23628 KB Output is correct
6 Correct 271 ms 23764 KB Output is correct
7 Correct 244 ms 23560 KB Output is correct
8 Correct 231 ms 23468 KB Output is correct
9 Correct 258 ms 23812 KB Output is correct
10 Correct 280 ms 23456 KB Output is correct
11 Correct 89 ms 18260 KB Output is correct
12 Correct 259 ms 23592 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 3 ms 11340 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 14 ms 14940 KB Output is correct
5 Correct 8 ms 13144 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 4 ms 11612 KB Output is correct
8 Correct 5 ms 11612 KB Output is correct
9 Correct 4 ms 11612 KB Output is correct
10 Correct 10 ms 13148 KB Output is correct
11 Correct 3 ms 11356 KB Output is correct
12 Correct 3 ms 11356 KB Output is correct
13 Correct 3 ms 11396 KB Output is correct
14 Correct 3 ms 11420 KB Output is correct
15 Correct 3 ms 11352 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 25108 KB Output is correct
2 Correct 257 ms 23596 KB Output is correct
3 Correct 260 ms 28384 KB Output is correct
4 Correct 230 ms 28540 KB Output is correct
5 Correct 258 ms 26900 KB Output is correct
6 Correct 236 ms 28688 KB Output is correct
7 Correct 249 ms 27436 KB Output is correct
8 Correct 234 ms 26896 KB Output is correct
9 Correct 222 ms 27848 KB Output is correct
10 Correct 168 ms 27708 KB Output is correct
11 Correct 74 ms 19540 KB Output is correct
12 Correct 215 ms 27744 KB Output is correct
13 Correct 282 ms 23688 KB Output is correct
14 Correct 232 ms 23624 KB Output is correct
15 Correct 239 ms 23476 KB Output is correct
16 Correct 230 ms 23608 KB Output is correct
17 Correct 250 ms 23628 KB Output is correct
18 Correct 271 ms 23764 KB Output is correct
19 Correct 244 ms 23560 KB Output is correct
20 Correct 231 ms 23468 KB Output is correct
21 Correct 258 ms 23812 KB Output is correct
22 Correct 280 ms 23456 KB Output is correct
23 Correct 89 ms 18260 KB Output is correct
24 Correct 259 ms 23592 KB Output is correct
25 Correct 11 ms 12888 KB Output is correct
26 Correct 3 ms 11340 KB Output is correct
27 Correct 3 ms 11356 KB Output is correct
28 Correct 14 ms 14940 KB Output is correct
29 Correct 8 ms 13144 KB Output is correct
30 Correct 3 ms 11612 KB Output is correct
31 Correct 4 ms 11612 KB Output is correct
32 Correct 5 ms 11612 KB Output is correct
33 Correct 4 ms 11612 KB Output is correct
34 Correct 10 ms 13148 KB Output is correct
35 Correct 3 ms 11356 KB Output is correct
36 Correct 3 ms 11356 KB Output is correct
37 Correct 3 ms 11396 KB Output is correct
38 Correct 3 ms 11420 KB Output is correct
39 Correct 3 ms 11352 KB Output is correct
40 Correct 228 ms 28548 KB Output is correct
41 Correct 259 ms 27708 KB Output is correct
42 Correct 226 ms 27744 KB Output is correct
43 Correct 94 ms 21680 KB Output is correct
44 Correct 141 ms 21756 KB Output is correct
45 Correct 223 ms 29060 KB Output is correct
46 Correct 252 ms 28928 KB Output is correct
47 Correct 223 ms 28620 KB Output is correct
48 Correct 108 ms 21076 KB Output is correct
49 Correct 240 ms 28288 KB Output is correct
50 Correct 230 ms 28148 KB Output is correct
51 Correct 220 ms 29192 KB Output is correct