oj.uz

Submission #338302

# Submission time Handle Problem Language Result Execution time Memory
338302 2020-12-22T22:18:21 Z gozonite Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 570 ms 25364 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef pair<int, int> pi;
#define MOD 1000000007LL

int N, M, S, T, U, V;
vector<pair<int, ll>> adj[100001];
ll disu[100001], disv[100001], diss[100001];
bool vis[100001];
bool indag[100001]={false};
ll dpu[100001], dpv[100001]; // shortest path from u/v to node in dag (where edges are 0 in dag --> cascade)

void dij(int s, ll (&dis)[100001]) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= N; i++) dis[i] = 1e18;
    dis[s] = 0;
    using T = pair<ll, ll>; priority_queue<T, vector<T>, greater<T>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second; q.pop();
        if (vis[v]) continue;
        vis[v] = true;
        for (auto pp : adj[v]) {
            ll u = pp.first, w = pp.second;
            if (dis[v]+w < dis[u]) {
                dis[u] = dis[v]+w;
                q.push({dis[u], u});
            }
        }
    }
}

void cdag(int v) {
    if (indag[v]) return;
    indag[v] = true;
    for (auto pp : adj[v]) {
        ll u = pp.first, w = pp.second;
        if (diss[u]+w == diss[v]) cdag(u);
    }
}

// starting from S to T
ll rdpu(int v) {
    if (dpu[v] != -1) return dpu[v];
    ll res = disu[v];
    for (auto pp : adj[v]) {
        ll u = pp.first, w = pp.second;
        if (indag[u] && diss[u]+w == diss[v]) res = min(res, rdpu(u));
    }
    return dpu[v] = res;
}

// starting from T to S
ll rdpv(int v) {
    if (dpv[v] != -1) return dpv[v];
    ll res = disv[v];
    for (auto pp : adj[v]) {
        ll u = pp.first, w = pp.second;
        if (indag[u] && diss[v]+w == diss[u]) res = min(res, rdpv(u));
    }
    return dpv[v] = res;
}

int main() {
    //freopen("feast.in", "r", stdin);
    //freopen("feast.out", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    
    cin >> N >> M >> S >> T >> U >> V;
    for (int i = 0; i < M; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    dij(U, disu); dij(V, disv); dij(S, diss);
    //cout << "Debugging dijkstras" << endl;
    //for (int i = 1; i <= N; i++) cout << disu[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << disv[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << diss[i] << " "; cout << endl;
    
    cdag(T);
    //cout << "Debugging nodes in dag" << endl;
    //for (int i = 1; i <= N; i++) cout << indag[i] << " "; cout << endl;
    
    for (int i = 1; i <= N; i++) {
        if (indag[i]) {
            dpu[i] = -1; //disu[i];
            dpv[i] = -1; //disv[i];
        } else {
            dpu[i] = 1e18;
            dpv[i] = 1e18;
        }
    }
    
    // first case: U is closer to S
    rdpu(T); rdpv(S);
    //cout << "Debugging dps" << endl;
    //for (int i = 1; i <= N; i++) cout << dpu[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << dpv[i] << " "; cout << endl;
    
    ll ans = disu[V];
    for (int i = 1; i <= N; i++)
        if (indag[i]) ans = min(ans, dpu[i]+dpv[i]);
        
    // second case: U is closer to T
    for (int i = 1; i <= N; i++) {
        if (indag[i]) {
            dpv[i] = -1;
            dpu[i] = -1;
        } else {
            dpv[i] = 1e18;
            dpu[i] = 1e18;
        }
    }
    swap(disu, disv);
    rdpu(T); rdpv(S);
    for (int i = 1; i <= N; i++)
        if (indag[i]) ans = min(ans, dpu[i]+dpv[i]);
    
    //cout << "Debugging dps2" << endl;
    //for (int i = 1; i <= N; i++) cout << dpu[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << dpv[i] << " "; cout << endl;
    
    cout << ans << endl;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 22508 KB Output is correct
2 Correct 461 ms 21104 KB Output is correct
3 Correct 541 ms 25308 KB Output is correct
4 Correct 441 ms 23008 KB Output is correct
5 Correct 485 ms 20852 KB Output is correct
6 Correct 448 ms 22820 KB Output is correct
7 Correct 528 ms 21000 KB Output is correct
8 Correct 508 ms 21252 KB Output is correct
9 Correct 459 ms 21876 KB Output is correct
10 Correct 428 ms 21708 KB Output is correct
11 Correct 250 ms 16620 KB Output is correct
12 Correct 507 ms 21580 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 22996 KB Output is correct
2 Correct 505 ms 23052 KB Output is correct
3 Correct 465 ms 22492 KB Output is correct
4 Correct 478 ms 22932 KB Output is correct
5 Correct 506 ms 23124 KB Output is correct
6 Correct 526 ms 24820 KB Output is correct
7 Correct 570 ms 25048 KB Output is correct
8 Correct 490 ms 22892 KB Output is correct
9 Correct 491 ms 23120 KB Output is correct
10 Correct 512 ms 22596 KB Output is correct
11 Correct 269 ms 18028 KB Output is correct
12 Correct 542 ms 25364 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6124 KB Output is correct
2 Correct 4 ms 4460 KB Output is correct
3 Correct 4 ms 4460 KB Output is correct
4 Correct 44 ms 7916 KB Output is correct
5 Correct 24 ms 6124 KB Output is correct
6 Correct 5 ms 4460 KB Output is correct
7 Correct 6 ms 4588 KB Output is correct
8 Correct 7 ms 4588 KB Output is correct
9 Correct 5 ms 4460 KB Output is correct
10 Correct 24 ms 6124 KB Output is correct
11 Correct 3 ms 4332 KB Output is correct
12 Correct 4 ms 4332 KB Output is correct
13 Correct 4 ms 4460 KB Output is correct
14 Correct 5 ms 4460 KB Output is correct
15 Correct 4 ms 4460 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 22508 KB Output is correct
2 Correct 461 ms 21104 KB Output is correct
3 Correct 541 ms 25308 KB Output is correct
4 Correct 441 ms 23008 KB Output is correct
5 Correct 485 ms 20852 KB Output is correct
6 Correct 448 ms 22820 KB Output is correct
7 Correct 528 ms 21000 KB Output is correct
8 Correct 508 ms 21252 KB Output is correct
9 Correct 459 ms 21876 KB Output is correct
10 Correct 428 ms 21708 KB Output is correct
11 Correct 250 ms 16620 KB Output is correct
12 Correct 507 ms 21580 KB Output is correct
13 Correct 495 ms 22996 KB Output is correct
14 Correct 505 ms 23052 KB Output is correct
15 Correct 465 ms 22492 KB Output is correct
16 Correct 478 ms 22932 KB Output is correct
17 Correct 506 ms 23124 KB Output is correct
18 Correct 526 ms 24820 KB Output is correct
19 Correct 570 ms 25048 KB Output is correct
20 Correct 490 ms 22892 KB Output is correct
21 Correct 491 ms 23120 KB Output is correct
22 Correct 512 ms 22596 KB Output is correct
23 Correct 269 ms 18028 KB Output is correct
24 Correct 542 ms 25364 KB Output is correct
25 Correct 25 ms 6124 KB Output is correct
26 Correct 4 ms 4460 KB Output is correct
27 Correct 4 ms 4460 KB Output is correct
28 Correct 44 ms 7916 KB Output is correct
29 Correct 24 ms 6124 KB Output is correct
30 Correct 5 ms 4460 KB Output is correct
31 Correct 6 ms 4588 KB Output is correct
32 Correct 7 ms 4588 KB Output is correct
33 Correct 5 ms 4460 KB Output is correct
34 Correct 24 ms 6124 KB Output is correct
35 Correct 3 ms 4332 KB Output is correct
36 Correct 4 ms 4332 KB Output is correct
37 Correct 4 ms 4460 KB Output is correct
38 Correct 5 ms 4460 KB Output is correct
39 Correct 4 ms 4460 KB Output is correct
40 Correct 441 ms 22552 KB Output is correct
41 Correct 447 ms 21628 KB Output is correct
42 Correct 444 ms 21820 KB Output is correct
43 Correct 317 ms 17260 KB Output is correct
44 Correct 323 ms 17260 KB Output is correct
45 Correct 526 ms 20792 KB Output is correct
46 Correct 517 ms 20528 KB Output is correct
47 Correct 419 ms 22736 KB Output is correct
48 Correct 293 ms 14828 KB Output is correct
49 Correct 377 ms 22168 KB Output is correct
50 Correct 499 ms 20820 KB Output is correct
51 Correct 522 ms 20884 KB Output is correct