tumaryui

Untitled

Sep 4th, 2020
1,032
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define endl "\n"
  5. using namespace std;
  6.  
  7. const int N = 3e5 + 10, inf = 1e16;
  8. vector<pair<int,int>> gr[N];
  9. vector<int> tin(N), tout(N), dep(N);
  10. int up[N][20], timer = 0, mup[N][20];
  11.  
  12. void calc(int v, int pr = 1, int w = inf) {
  13. up[v][0] = pr;
  14. mup[v][0] = min(mup[v][0], w);
  15. tin[v] = timer++;
  16. for(int i = 1; i < 20; i++) {
  17. up[v][i] = up[up[v][i - 1]][i - 1];
  18. mup[v][i] = min(mup[v][i - 1], mup[up[v][i - 1]][i - 1]);
  19. }
  20. for(auto it: gr[v]) {
  21. int to = it.first;
  22. int w = it.second;
  23. if(to != pr) {
  24. dep[to] = dep[v] + 1;
  25. calc(to, v, w);
  26. }
  27. }
  28. tout[v] = timer++;
  29. }
  30. bool upper(int a, int b) {
  31. return tin[a] <= tin[b] && tout[a] >= tout[b];
  32. }
  33. int lca(int a, int b) {
  34. if(upper(a, b)) return a;
  35. if(upper(b, a)) return b;
  36. for(int i = 19; i >= 0; i--) {
  37. if(!upper(up[a][i], b)) {
  38. a = up[a][i];
  39. }
  40. }
  41. return up[a][0];
  42. }
  43. int dist(int a, int b) {
  44. return dep[a] + dep[b] - 2 * dep[lca(a, b)];
  45. }
  46.  
  47. int parmin(int l, int r) {
  48. int res = inf;
  49. for(int i = 19; i >= 0; i--) {
  50. if(r == l) break;
  51. if(upper(r, up[l][i])) {
  52. res = min(res, mup[l][i]);
  53. l = up[l][i];
  54. }
  55. }
  56. return res;
  57. }
  58.  
  59. int getmin(int l, int r) {
  60. int mid = lca(l, r);
  61. int ans = inf;
  62. ans = min(parmin(l, mid), parmin(r, mid));
  63. return ans;
  64. }
  65.  
  66. main() {
  67. ios_base::sync_with_stdio(0);
  68. cin.tie(0);
  69. cout.tie(0);
  70. int n, m;
  71. cin >> n >> m;
  72. for(int i = 0; i <= n; i++) {
  73. for(int j = 0; j < 20; j++) {
  74. mup[i][j] = inf;
  75. }
  76. }
  77. for(int i = 1; i <= m; i++) {
  78. int l, r, w;
  79. cin >> l >> r >> w;;
  80. gr[l].pb({r, w});
  81. gr[r].pb({l, w});
  82. }
  83. calc(1);
  84. int q;
  85. cin >> q;
  86. while(q--) {
  87. int l, r;
  88. cin >> l >> r;
  89. cout << getmin(l, r) << endl;
  90. }
  91. }
Advertisement
Comments
  • User was banned
Add Comment
Please, Sign In to add comment