st表 + 变形的djs （好题

https://codeforces.com/gym/105386/problem/J

#include <bits/stdc++.h>using i64 = long long;struct STList {int n, k;std::vector<std::vector<int>> Max;STList() {}STList(const std::vector<int>&a) {init(a);}void init(const std::vector<int>&a) {n = a.size();k = std::__lg(n) + 1;Max.assign(n, std::vector<int>(k));for (int i = 0; i < n; ++i) {Max[i][0] = a[i];}for (int j = 1; j < k; ++j) {for (int i = 0; i + (1 << j) <= n; ++i) Max[i][j] = std::max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);}}int query(int l, int r) {int j = std::__lg(r - l + 1);return std::max(Max[l][j], Max[r - (1 << j) + 1][j]);}
};void Solve() {int n, m, K;std::cin >> n >> m >> K;std::vector<std::vector<std::array<int, 3>>> adj(n);for (int i = 0; i < m; ++i) {int x, y, c, l;std::cin >> x >> y >> c >> l;x--, y--, c--;adj[x].push_back({y, c, l});adj[y].push_back({x, c, l});}std::vector<std::vector<int>> pos(m), len(m);std::vector<int> L(K), col(K);for (int i = 0; i < K; ++i) {int c, l;std::cin >> c >> l;c--;pos[c].push_back(i);len[c].push_back(l);col[i] = c;L[i] = l;}std::vector<STList> f(m);for (int i = 0; i < m; ++i) {if (pos[i].size() == 0) {continue;}f[i].init(len[i]);}std::priority_queue<std::array<int, 3>, std::vector<std::array<int, 3>>, std::greater<>> q;q.push({0, 0, 0});std::vector<int> vis(n);while (!q.empty()) {auto [p, t, x] = q.top(); // ticket, remain distanceq.pop();if (vis[x]) {continue;}vis[x] = 1;// std::cerr << p << ' ' << t << ' ' << x << '\n';for (auto [y, c, l] : adj[x]) {// std::cerr << "y, c, l = " << y << ' ' << c << ' ' << l <<   '\n';if (pos[c].size() == 0) continue;if (c == col[p] && l <= L[p] - t) {q.push({p, t + l, y});continue;}auto it = std::upper_bound(pos[c].begin(), pos[c].end(), p) - pos[c].begin();if (it == pos[c].size()) {continue;}int v = it;int lo = it, hi = pos[c].size() - 1;if (f[c].query(lo, hi) < l) {continue;}// std::cerr << "binary search!\n";while (lo < hi) {int mid = (lo + hi) / 2;if (f[c].query(v, mid) >= l) {hi = mid;} else {lo = mid + 1;}}q.push({pos[c][lo], l, y});}}for (int i = 0; i < n; ++i) {std::cout << vis[i];}std::cout << '\n';
}int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;for (int ti = 1; ti <= t; ++ti) {// std::cerr << "Solve : " << ti << '\n';Solve(); }return 0;
}