当前位置: 首页 > news >正文

st表 + 变形的djs (好题

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;
}
http://www.hskmm.com/?act=detail&tid=25043

相关文章:

  • 2025年微信小程序开发:AR/VR与电商的最新案例 - 指南
  • 10.5
  • 在wpf .net 8项目中使用materialDesign 4 以上版本的的注意事项
  • 学习STC51单片机26(芯片为STC89C52RCRC) - 实践
  • 洛谷P14120 题解 - lemon
  • cf41d
  • 33 ACwing 294 Count The Repetitions 题解
  • 电赛电装实习总结
  • 30 ACwing 291 蒙德里安的梦想 题解
  • 21 ACwing 289 环路运输 题解
  • 26 UVA1630 串折叠 Folding 题解
  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解