Submission #881340

#	Time	Username	Problem	Language	Result	Execution time	Memory
881340		_KuroNeko_	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	247 ms	30632 KiB

commuter_pass

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vdb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef set<int> si;
typedef set<long long> sl;
typedef set<double> sdb;
typedef set<string> ss;
typedef set<char> sc;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ftb(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define ft(i, a, b) for (int i = a, _b = b; i < _b; ++i)
#define fgb(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define fg(i, a, b) for (int i = a, _b = b; i > _b; --i)
#define endl "\n"
void dijkstra(int node, vector<pll> adj[], vl& distance) {
    distance[node] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({ 0,node });
    while (!q.empty()) {
        int node = q.top().second;
        ll d = q.top().first;
        q.pop();
        if (d > distance[node]) continue;
        for (pll it : adj[node]) {
            if (distance[it.first] > d + it.second) {
                distance[it.first] = d + it.second;
                q.push({ d + it.second,it.first });
            }
        }
    }
}
void dijkstra2(int node, vector<pll> adj[], vl parent[], int n) {
    vl distance(n + 1, 1e17);
    distance[node] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({ 0,node });
    while (!q.empty()) {
        int node = q.top().second;
        ll d = q.top().first;
        q.pop();
        if (d > distance[node]) continue;
        for (pll it : adj[node]) {
            if (distance[it.first] > d + it.second) {
                distance[it.first] = d + it.second;
                q.push({ d + it.second,it.first });
                parent[it.first].clear();
                parent[it.first].push_back(node);
            }
            else if (distance[it.first] == d + it.second) {
                parent[it.first].push_back(node);
            }
        }
    }
}
void bfs(int n, int s, vl adj[], vl& disU, vl& disV, ll& ans) {
    vi cnt(n + 1, 0);
    ftb(i, 1, n) {
        for (int it : adj[i]) {
            cnt[it] += 1;
        }
    }
    queue<int> q;
    vl mn(n + 1, 0);
    ftb(i, 1, n) {
        mn[i] = disU[i];
    }
    q.push(s);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        ans = min(ans, mn[node] + disV[node]);
        for (int it : adj[node]) {
            cnt[it] -= 1;
            mn[it] = min(mn[it], mn[node]);
            if (cnt[it] == 0) {
                q.push(it);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("C:\\Users\\tring\\Downloads\\2018-ho-data\\2018-ho-data\\2018-ho-t4\\in\\03-01.txt", "r", stdin);
    ll n, m;
    cin >> n >> m;
    ll s, t, u, v;
    cin >> s >> t >> u >> v;
    vector<pll> adj[n + 1];
    ft(i, 0, m) {
        ll x, y, z;
        cin >> x >> y >> z;
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    vl disU(n + 1, 1e17), disV(n + 1, 1e17);
    dijkstra(u, adj, disU);
    dijkstra(v, adj, disV);
    vl parent[n + 1];
    vl adj2[n + 1];
    queue<int> q;
    q.push(t);
    vector<bool> check(n + 1, false);
    dijkstra2(s, adj, parent, n);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int it : parent[node]) {
            if (!check[it]) {
                check[it] = true;
                q.push(it);
            }
            adj2[it].push_back(node);
        }
    }
    ll ans = disU[v];
    bfs(n, s, adj2, disU, disV, ans);
    bfs(n, s, adj2, disV, disU, ans);
    cout << ans << endl;
}

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