oj.uz

Submission #895889

# Submission time Handle Problem Language Result Execution time Memory
895889 2023-12-31T03:07:12 Z niter Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 264 ms 32464 KB 
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
//#define op(x) cerr << #x << " = " << x << endl;
//#define opa(x) cerr << #x << " = " << x << ", ";
//#define ops(x) cerr << x;
//#define entr cerr << endl;
//#define spac cerr << ' ';
//#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
//#define ARR(x, nnn) cerr << #x <<  " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) x.begin(), x.end()
#define unilize(x) x.resize(unique(BAE(x)) - x.begin())
#define unisort(x) sort(BAE(x)); unilize(x);
using namespace std;
typedef long long ll;

const int mxn = (int)(1e5) + 10;
const ll INF = 1e18;
struct EDGE{ int u, w; };
struct three_edge{ int ff, ss, w; };
vector<EDGE> E[mxn], F[mxn], G[mxn];
ll dp[mxn], d1[mxn], d2[mxn];
vector<three_edge> EV;
bool vis[mxn], n_vis[mxn];

void dfs(int v){
    vis[v] = true;
    for(auto &i:F[v]){
        if(!vis[i.u]){
            dfs(i.u);
        }
    }
}
void n_dfs(int v){
    n_vis[v] = true;
    for(auto &i:G[v]){
        if(!n_vis[i.u]){
            n_dfs(i.u);
        }
    }
}

int main(){
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    loop(i,0,m){
        int ia, ib, w;
        cin >> ia >> ib >> w;
        E[ia].pb({ib, w});
        E[ib].pb({ia, w});
        EV.pb({ia, ib, w});
    }
    loop(i,1,n+1) dp[i] = INF; dp[S] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, S});
    while(!pq.empty()){
        int now = pq.top().ss;
        ll dis = pq.top().ff;
        pq.pop();
        if(dis != dp[now]) continue;
        for(auto &i:E[now]){
            if(dis + i.w < dp[i.u]){
                dp[i.u] = dis + i.w;
                pq.push({dp[i.u], i.u});
            }
        }
    }
    for(auto &i:EV){
        if(min(dp[i.ff], dp[i.ss]) + i.w == max(dp[i.ff], dp[i.ss])){
            int near = (dp[i.ff] < dp[i.ss]) ? i.ff : i.ss;
            int far = i.ff + i.ss - near;
            F[near].pb({far, 0});
//            opa(far) op(near)
//            opa(near) op(far)
            G[far].pb({near, 0});
        }
    }
    dfs(S);
    n_dfs(T);
    loop(i,1,n+1){
        F[i].clear();
        G[i].clear();
    }
    for(auto &i:EV){
        if(min(dp[i.ff], dp[i.ss]) + i.w == max(dp[i.ff], dp[i.ss])
           && vis[i.ff] && vis[i.ss] && n_vis[i.ff] && n_vis[i.ss]){
            int near = (dp[i.ff] < dp[i.ss]) ? i.ff : i.ss;
            int far = i.ff + i.ss - near;
            F[near].pb({far, 0});
            G[far].pb({near, 0});
        }
    }
    loop(i,1,n+1) dp[i] = INF; dp[U] = 0;
    pq.push({0, U});
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != dp[now]) continue;
        for(auto &i:E[now]){
            if(dp[i.u] > nd + i.w){
                dp[i.u] = nd + i.w;
                pq.push({dp[i.u], i.u});
            }
        }
    }
    ll ans = dp[V];
    loop(i,1,n+1){
        d1[i] = dp[i];
        pq.push({d1[i], i});
    }
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != d1[now]) continue;
        for(auto &i:F[now]){
            if(d1[i.u] > nd + i.w){
                d1[i.u] = nd + i.w;
                pq.push({d1[i.u], i.u});
            }
        }
    }
    loop(i,1,n+1){
        d2[i] = dp[i];
        pq.push({d2[i], i});
    }
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != d2[now]) continue;
        for(auto &i:G[now]){
            if(d2[i.u] > nd + i.w){
                d2[i.u] = nd + i.w;
                pq.push({d2[i.u], i.u});
            }
        }
    }
    loop(i,1,n+1){
        dp[i] = min(d1[i], d2[i]);
        pq.push({dp[i], i});
    }
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != dp[now]) continue;
        for(auto &i:E[now]){
            if(dp[i.u] > nd + i.w){
                dp[i.u] = nd + i.w;
                pq.push({dp[i.u], i.u});
            }
        }
    }
    ans = min(ans, dp[V]);
    cout << ans << '\n';
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:2:21: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    2 | #define loop(i,a,b) for(int i = (a); i < (b); i ++)
      |                     ^~~
commuter_pass.cpp:59:5: note: in expansion of macro 'loop'
   59 |     loop(i,1,n+1) dp[i] = INF; dp[S] = 0;
      |     ^~~~
commuter_pass.cpp:59:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |     loop(i,1,n+1) dp[i] = INF; dp[S] = 0;
      |                                ^~
commuter_pass.cpp:2:21: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    2 | #define loop(i,a,b) for(int i = (a); i < (b); i ++)
      |                     ^~~
commuter_pass.cpp:99:5: note: in expansion of macro 'loop'
   99 |     loop(i,1,n+1) dp[i] = INF; dp[U] = 0;
      |     ^~~~
commuter_pass.cpp:99:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   99 |     loop(i,1,n+1) dp[i] = INF; dp[U] = 0;
      |                                ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 28816 KB Output is correct
2 Correct 228 ms 30332 KB Output is correct
3 Correct 226 ms 31864 KB Output is correct
4 Correct 193 ms 30404 KB Output is correct
5 Correct 233 ms 31320 KB Output is correct
6 Correct 198 ms 28484 KB Output is correct
7 Correct 263 ms 30684 KB Output is correct
8 Correct 230 ms 30384 KB Output is correct
9 Correct 219 ms 30460 KB Output is correct
10 Correct 198 ms 30232 KB Output is correct
11 Correct 132 ms 26628 KB Output is correct
12 Correct 221 ms 30964 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 30708 KB Output is correct
2 Correct 216 ms 30716 KB Output is correct
3 Correct 234 ms 30384 KB Output is correct
4 Correct 215 ms 30460 KB Output is correct
5 Correct 217 ms 30240 KB Output is correct
6 Correct 235 ms 31736 KB Output is correct
7 Correct 247 ms 31992 KB Output is correct
8 Correct 264 ms 30436 KB Output is correct
9 Correct 251 ms 30756 KB Output is correct
10 Correct 233 ms 30572 KB Output is correct
11 Correct 142 ms 26656 KB Output is correct
12 Correct 219 ms 32116 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11416 KB Output is correct
2 Correct 2 ms 10072 KB Output is correct
3 Correct 3 ms 9860 KB Output is correct
4 Correct 13 ms 12896 KB Output is correct
5 Correct 7 ms 11160 KB Output is correct
6 Correct 3 ms 9900 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 4 ms 10072 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 7 ms 11240 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 10072 KB Output is correct
13 Correct 3 ms 9888 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 3 ms 9892 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 28816 KB Output is correct
2 Correct 228 ms 30332 KB Output is correct
3 Correct 226 ms 31864 KB Output is correct
4 Correct 193 ms 30404 KB Output is correct
5 Correct 233 ms 31320 KB Output is correct
6 Correct 198 ms 28484 KB Output is correct
7 Correct 263 ms 30684 KB Output is correct
8 Correct 230 ms 30384 KB Output is correct
9 Correct 219 ms 30460 KB Output is correct
10 Correct 198 ms 30232 KB Output is correct
11 Correct 132 ms 26628 KB Output is correct
12 Correct 221 ms 30964 KB Output is correct
13 Correct 247 ms 30708 KB Output is correct
14 Correct 216 ms 30716 KB Output is correct
15 Correct 234 ms 30384 KB Output is correct
16 Correct 215 ms 30460 KB Output is correct
17 Correct 217 ms 30240 KB Output is correct
18 Correct 235 ms 31736 KB Output is correct
19 Correct 247 ms 31992 KB Output is correct
20 Correct 264 ms 30436 KB Output is correct
21 Correct 251 ms 30756 KB Output is correct
22 Correct 233 ms 30572 KB Output is correct
23 Correct 142 ms 26656 KB Output is correct
24 Correct 219 ms 32116 KB Output is correct
25 Correct 10 ms 11416 KB Output is correct
26 Correct 2 ms 10072 KB Output is correct
27 Correct 3 ms 9860 KB Output is correct
28 Correct 13 ms 12896 KB Output is correct
29 Correct 7 ms 11160 KB Output is correct
30 Correct 3 ms 9900 KB Output is correct
31 Correct 3 ms 9816 KB Output is correct
32 Correct 4 ms 10072 KB Output is correct
33 Correct 3 ms 9820 KB Output is correct
34 Correct 7 ms 11240 KB Output is correct
35 Correct 3 ms 9820 KB Output is correct
36 Correct 3 ms 10072 KB Output is correct
37 Correct 3 ms 9888 KB Output is correct
38 Correct 3 ms 9820 KB Output is correct
39 Correct 3 ms 9892 KB Output is correct
40 Correct 180 ms 28280 KB Output is correct
41 Correct 205 ms 30228 KB Output is correct
42 Correct 192 ms 30568 KB Output is correct
43 Correct 148 ms 26612 KB Output is correct
44 Correct 152 ms 26644 KB Output is correct
45 Correct 234 ms 31560 KB Output is correct
46 Correct 242 ms 31364 KB Output is correct
47 Correct 224 ms 32464 KB Output is correct
48 Correct 129 ms 25348 KB Output is correct
49 Correct 173 ms 29308 KB Output is correct
50 Correct 262 ms 31504 KB Output is correct
51 Correct 221 ms 31644 KB Output is correct