Submission #1239369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239369		yarh	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	221 ms	55156 KiB

commuter_pass

#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <numeric>
#include <initializer_list>
#include <string>
#include <variant>
#include <set>
#include <bitset>
#include <climits>
#include <stack>


typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = INT_MAX;
const int INV2 = 500000004;
using namespace std;

// segment tree odd length omodel 

//   1 
//    2
// 3 4 5 

// so if left side is odd, then I need to --l / 2 to get the parent 

//   2   
//     3  4 
// 5 6 7 8 9 


// input
// 10
// 10 3 9 5 2 10 5 9 2 1

struct SegmentTree {
    vector<int> tree; 
    int n; 

    SegmentTree(int n) {
        this->tree = vector<int>(2 * n, 0); 
        this->n = n; 
    }

    void update(int index, int val) {
        int _index = this->n + index; 
        this->tree[_index] = (this->tree[_index] + val) % MOD; 

        while (_index > 1) {
            _index /= 2; 
            this->tree[_index] = (this->tree[_index * 2] + this->tree[_index * 2 + 1]) % MOD; 
        }
    }

    // queries range [l, r)
    int query(int l, int r) {
        int res = 0; 
        
        l += this->n; 
        r += this->n; 

        while (l < r) {
            if (l % 2 == 1) res = (res + this->tree[l++]) % MOD; 
            if (r % 2 == 1) res = (res + this->tree[--r]) % MOD; 

            l /= 2; 
            r /= 2; 
        }

        return res; 
    }

    void print() {
        cout << "n: " << n << endl;
        cout << "tree: "; 
        for (auto x : this->tree) cout << x << " ";
        cout << endl; 
        cout << endl; 
    }
};

struct DSU {
    vector<int> parent;
    vector<int> num_components; 

    DSU(int n) {
        parent = vector<int>(n + 1, 0); 
        for (int i = 0; i <= n; ++i) parent[i] = i; 

        num_components = vector<int>(n + 1, 1); 
    }

    int find(int i) {
        if (parent[i] != i) {
            parent[i] = this->find(parent[i]); 
            return parent[i]; 
        }
        return parent[i]; 
    }

    int query(int i) {
        int root = this->find(i); 
        return num_components[root]; 
    }

    void merge(int i, int j) {
        int root_i = this->find(i); 
        int root_j = this->find(j); 

        int num_component_i = num_components[root_i]; 
        int num_component_j = num_components[root_j]; 

        if (rand() % 2) swap(root_i, root_j); 

        parent[root_i] = root_j; 
        num_components[root_j] = num_component_i + num_component_j; 
    }
};


void solve() {
    int n, m; cin >> n >> m; 
    int s, t; cin >> s >> t; 
    int u, v; cin >> u >> v; 

    vector<vector<pair<int, ll>>> adj(n + 1); 
    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 }); 
    }

    vector<vector<int>> prev(n + 1); // previous nodes for dijkstras 

    {
        vector<ll> dist(n + 1, LLONG_MAX);

        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
        que.push({ 0, s });
        dist[s] = 0;

        while (!que.empty()) {
            auto [weight, node] = que.top();
            que.pop();
            // cout << "processing " << weight << " " << node << endl;

            if (dist[node] < weight) continue;


            for (auto [next, next_weight] : adj[node]) {
                ll alt = weight + next_weight;
                if (alt == dist[next]) {
                    prev[next].push_back(node);
                }
                else if (alt < dist[next]) {
                    prev[next].clear(); prev[next].push_back(node); 
                    dist[next] = alt;
                    que.push({ dist[next], next });
                }
            }
        }
    }

    // now recover the subgraph? 
    vector<vector<pair<int, ll>>> adj_f(adj);
    vector<vector<pair<int, ll>>> adj_r(adj);

    {
        queue<int> que;
        vector<bool> visited(n + 1, false);

        que.push(t);
        visited[t] = true; 

        while (!que.empty()) {
            int node = que.front(); 
            que.pop(); 

            if (node == s) break; 

            for (int prev_node : prev[node]) {
                if (!visited[prev_node]) {
                    que.push(prev_node); 
                    adj_f[prev_node].push_back({ node, 0 }); // train pass
                    adj_r[node].push_back({ prev_node, 0 }); // train pass 
                }
            }
        }
    }

    
    // now dijkstra again to find actual distance from u to v
    vector<ll> dist_f(n + 1, LLONG_MAX);
    {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que; 
        que.push({ 0, u }); 
        dist_f[u] = 0; 

        while (!que.empty()) {
            auto [weight, node] = que.top(); 
            que.pop(); 

            if (dist_f[node] < weight) continue; 

            for (auto [next, next_weight] : adj_f[node]) {
                ll alt = weight + next_weight; // negative to simplify pq declaration
                if (alt < dist_f[next]) {
                    dist_f[next] = alt; 
                    que.push({ dist_f[next], next});
                }
            }
        }
    }


    vector<ll> dist_r(n + 1, LLONG_MAX);
    {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que;
        que.push({ 0, u });
        dist_r[u] = 0;

        while (!que.empty()) {
            auto [weight, node] = que.top();
            que.pop();

            if (dist_r[node] < weight) continue;

            for (auto [next, next_weight] : adj_r[node]) {
                ll alt = weight + next_weight; // negative to simplify pq declaration
                if (alt < dist_r[next]) {
                    dist_r[next] = alt;
                    que.push({ dist_r[next], next });
                }
            }
        }
    }

    // cout << dist_f[v] << " " << dist_r[v] << endl;
    cout << min(dist_f[v], dist_r[v]) << endl;
}

int main() {
    // usaco
    // freopen("mootube.in", "r", stdin);
    // freopen("mootube.out", "w", stdout);

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();

    return 0; 
}

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45