ABC212F - Greedy Takahashi

問題

https://atcoder.jp/contests/abc212/tasks/abc212_f

略説

高橋君の時刻0から時刻Zまでの行動は一意に定まる

"高橋君がk番目に乗ったバスを乗り終わった時刻t<Z"を満たす最大のKが求まれば、適切に場合分けをすることで、時刻Zでの高橋君の状態も求まる

kは0からMの範囲を二分探索することで求められる

"バスiを乗り終わってから2^j番目に乗るバス"を前計算(O(MlogM))しておくことで、kを決めたとき、初期状態からk番目に乗ったバスはO(logM)で求められる(ダブリング)

つまり二分探索の判定パート(t<Z)はO(logM)で行える

よって計算量はO(MlogM+QloglogM)となる

また、一回もバスに乗らずに時刻Zを迎えるケースがあるが、これも適切に場合分けをしておけばよい

ACコード

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

int N, M, Q;
int A[1<<17], B[1<<17], S[1<<17], T[1<<17];
vector<pair<int,int>> G[1<<17];
int dp[1<<17][17];

int next_bus(int city, int time) {
    auto nxt = lower_bound(G[city].begin(), G[city].end(), make_pair(time,-1));
    if (nxt == G[city].end()) return -1;
    return nxt->second;
}

int warp(int s, int x) {
    int pos = s;
    for (int i=0; i<17; i++) if (x&(1<<i)) pos = dp[pos][i];
    return pos;
}

void solve() {
    cin >> N >> M >> Q;
    for (int i=0; i<M; i++) {
        cin >> A[i] >> B[i] >> S[i] >> T[i];
        A[i]--, B[i]--;
        G[A[i]].push_back(make_pair(S[i], i));
    }
    for (int i=0; i<N; i++) sort(G[i].begin(), G[i].end());
    for (int i=0; i<M; i++) {
        int nxt = next_bus(B[i], T[i]);
        dp[i][0] = nxt<0?i:nxt;
    }
    for (int i=1; i<17; i++) for (int j=0; j<M; j++) {
        dp[j][i] = dp[dp[j][i-1]][i-1];
    }
    while (Q--) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        Y--;
        int fst = next_bus(Y, X);
        if (fst<0 || Z<=S[fst]) {
            cout << Y+1 << '\n';
            continue;
        }
        if (Z <= T[fst]) {
            cout << Y+1 << ' ' << B[fst]+1 << '\n';
            continue;
        }
        int left = 0, right = M;
        while (right-left > 1) {
            int mid = left+(right-left)/2;
            if (T[warp(fst, mid)] < Z) left = mid;
            else right = mid;
        }
        int pos = warp(fst, left);
        int nxt = next_bus(B[pos], T[pos]);
        if (nxt<0 || Z<=S[nxt]) cout << B[pos]+1 << '\n';
        else cout << A[nxt]+1 << ' ' << B[nxt]+1 << '\n';
    }
}

signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}