TIOJ 2196：D. 乘車時間

TIOJ 2196：D. 乘車時間

題目大意：有 $n$ 個地鐵站，$n - 1$ 條路線 (一棵樹)，每條路線的兩個車站 $x, y$ 有自己的出車時間 $a, b$，可能為 $0$ 點 $0\sim 5$ 分鐘，發車間距為 $p$，可能為 $1\sim 6$ 分鐘，及開車時長 $w$ 分鐘及換車時間 $1$ 分鐘。每次給你兩個點 $x, y$ 及出發時間 $h$ 點 $m$ 分，問從 $x$ 到 $y$ 最少的時間。

解法：其實換車的時間可以加在開車時長裡，反正沒差，然後可以觀察到，$lcm (1\sim 6) = 60$，相當於 $1$ 小時，所以輸入的 $h$ 其實可以不用管。剩下的部分我們可以做 $lca$，把 $a$ 到 $b$ 的路拆成 $a$ 到祖先的路和祖先到 $b$ 的路，最後總和減 $1$。需要維護如果在 $t$ 分到達車站 $x$，那到 $x$ 的 $2^{cnt}$ 祖先需要花的時長，並且分向上和向下維護，這樣差不多就可以 $\text{AC}$ 了！

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e4 + 5;
const int H = __lg (SIZE) + 1;

int n, q;
int h[SIZE], to[SIZE][H + 1], up[SIZE][H + 1][60], down[SIZE][H + 1][60];
vector<tuple<int, int, int, int, int>> adj[SIZE];

int trans (int a, int p, int t) {return (a - t + 60) % p;}
void dfs (int pos, int fa) {
    for (auto [np, w, a, b, p] : adj[pos]) {
        if (np == fa) {
            continue;
        }
        h[np] = h[pos] + 1;
        to[np][0] = pos;
        FOR (i, 0, 59) {
            up[np][0][i] = trans (b, p, i) + w;
            down[np][0][i] = trans (a, p, i) + w;
        }
        dfs (np, pos);
    }
}

int jump (int pos, int k) {int cnt = 0; while (k) {if (k & 1) {pos = to[pos][cnt];} cnt++; k >>= 1;} return pos;}
int lca (int a, int b) {
    if (h[a] < h[b]) {
        swap (a, b);
    }
    a = jump (a, h[a] - h[b]);
    if (a == b) {
        return a;
    }
    for (int i = H; i >= 0; i--) {
        if (to[a][i] != to[b][i]) {
            a = to[a][i];
            b = to[b][i];
        }
    }
    return to[a][0];
}

int cal (int pos, int k, int &m, bool ty) { // ty = 0 : go up, ty = 1 : go down
    int re = 0, cnt = 0;
    if (ty == 0) {
        while (k) {
            if (k & 1) {
                re += up[pos][cnt][m];
                m = (m + up[pos][cnt][m]) % 60;
                pos = to[pos][cnt];
            }
            cnt++;
            k >>= 1;
        }
    } else {
        vector<pair<int, int>> v;
        while (k) {
            if (k & 1) {
                v.pb (cnt, pos);
                pos = to[pos][cnt];
            }
            cnt++;
            k >>= 1;
        }
        reverse (v.begin(), v.end());
        for (auto [c, p] : v) {
            re += down[p][c][m];
            m = (m + down[p][c][m]) % 60;
        }
    }
    return re;
}

void solve() {
    cin >> n >> q;
    FOR (i, 2, n) {
        int x, y, w, a, b, p;
        cin >> x >> y >> w >> a >> b >> p;
        adj[x].pb (y, w + 1, a, b, p);
        adj[y].pb (x, w + 1, b, a, p);
    }
    dfs (1, 1);
    FOR (i, 1, H) FOR (j, 1, n) {
        int fa = to[j][i - 1];
        if (fa == 0) {
            continue;
        }
        to[j][i] = to[fa][i - 1];
        FOR (t, 0, 59) {
            up[j][i][t] = up[j][i - 1][t] + up[fa][i - 1][ (t + up[j][i - 1][t]) % 60];
            down[j][i][t] = down[fa][i - 1][t] + down[j][i - 1][ (t + down[fa][i - 1][t]) % 60];
        }
    }
    while (q--) {
        int m, a, b, root;
        cin >> m >> m >> a >> b;
        root = lca (a, b);
        cout << cal (a, h[a] - h[root], m, 0) + cal (b, h[b] - h[root], m, 1) - 1 << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！