提出 #36027453

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    vector<array<int, 4>> bus(m);
    vector<vector<pair<int, int>>> state(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, s, t;
        cin >> u >> v >> s >> t;
        bus[i] = {u, v, s, t};
        state[u].push_back({s, i});
    }

    for (int i = 1; i <= n; ++i) {
        sort(state[i].begin(), state[i].end());
    }

    int mm = log2(m) + 1;
    auto f = vector(m, vector(mm, -1));

    auto get = [&](int p, int t) {
        auto it = lower_bound(state[p].begin(), state[p].end(), make_pair(t, 0));

        if (it == state[p].end())
            return -p;

        return it->second;
    };

    for (int i = 0; i < m; ++i) {
        f[i][0] = get(bus[i][1], bus[i][3]);
    }

    for (int i = 1; i < mm; ++i) {
        for (int j = 0; j < m; ++j) {
            if (f[j][i - 1] >= 0)
                f[j][i] = f[f[j][i - 1]][i - 1];
            else
                f[j][i] = f[j][i - 1];
        }
    }

    for (int i = 1; i <= k; ++i) {
        int t1, u, t2;
        cin >> t1 >> u >> t2;
        int a = get(u, t1);
        //cout << "a = " << a << endl;

        if (a < 0 || bus[a][2] >= t2) {
            cout << u << "\n";
            continue;
        }

        for (int i = mm - 1; i >= 0; --i) {
            auto b = f[a][i];

            if (b >= 0 && bus[b][2] < t2)
                a = b;
        }

        if (bus[a][3] >= t2) {
            cout << bus[a][0] << " " << bus[a][1] << "\n";
        } else {
            cout << bus[a][1] << "\n";
        }
    }

    return 0;
}

提出情報

ジャッジ結果