fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pp push_back
  5. #define endl '\n'
  6. #define all(x) x.begin(),x.end()
  7. #define ld long double
  8. #define PI acos(-1)
  9. #define ones(x) __builtin_popcountll(x)
  10. //#define int ll
  11.  
  12. using namespace std;
  13.  
  14. void Drakon() {
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.     cout.tie(nullptr);
  18. #ifdef Clion
  19.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  20. #endif
  21. }
  22.  
  23. unsigned long long inf = 1e10;
  24. const double EPS = 1e-6;
  25. const int MOD = 1000000007, N = 1e6 + 5, LOG = 22;
  26.  
  27. ll mul(const ll &a, const ll &b) {
  28.     return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
  29. }
  30.  
  31. ll add(const ll &a, const ll &b) {
  32.     return (a + b + 2 * MOD) % MOD;
  33. }
  34.  
  35. ll pw(ll x, ll y) {
  36.     ll ret = 1;
  37.     while (y > 0) {
  38.         if (y % 2 == 0) {
  39.             x = mul(x, x);
  40.             y = y / 2;
  41.         } else {
  42.             ret = mul(ret, x);
  43.             y = y - 1;
  44.         }
  45.     }
  46.     return ret;
  47. }
  48.  
  49. vector<pair<int, int>> adj[N];
  50. int depth[N], up[N][LOG], dist[N][LOG], n;
  51.  
  52. struct DSU {
  53.     vector<int> par, sz;
  54.  
  55.     DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
  56.  
  57.     int find(int x) {
  58.         if (x == par[x])return x;
  59.         return par[x] = find(par[x]);
  60.     }
  61.  
  62.     bool same(int x, int y) { return find(x) == find(y); }
  63.  
  64.     bool join(int x, int y) {
  65.         x = find(x);
  66.         y = find(y);
  67.         if (x == y) return false;
  68.         if (sz[x] < sz[y])
  69.             swap(x, y);
  70.         sz[x] += sz[y];
  71.         par[y] = x;
  72.         return true;
  73.     }
  74.  
  75.     int size(int x) { return sz[find(x)]; }
  76. };
  77.  
  78. bool vis[N];
  79. void dfs(int u, int p) {
  80.     vis[u] = true;
  81.     for (auto v: adj[u]) {
  82.         if (v.first == p)continue;
  83.         depth[v.first] = depth[u] + 1;
  84.         dist[v.first][0] = v.second;
  85.         up[v.first][0] = u;
  86.         dfs(v.first, u);
  87.     }
  88. }
  89.  
  90. int get_lca(int a, int b) {
  91.     if (depth[a] < depth[b])
  92.         swap(a, b);
  93.     int k = depth[a] - depth[b];
  94.     for (int i = 0; i < LOG; ++i) {
  95.         if ((1 << i) & k) {
  96.             a = up[a][i];
  97.         }
  98.     }
  99.     if (a == b)
  100.         return a;
  101.     for (int i = LOG - 1; i >= 0; --i) {
  102.         if (up[a][i] != up[b][i]) {
  103.             a = up[a][i];
  104.             b = up[b][i];
  105.         }
  106.     }
  107.     return up[a][0];
  108. }
  109.  
  110. void build() {
  111.     for (int i = 0; i < n; ++i) {
  112.         if(vis[i]) continue;
  113.         up[i][0] = i;
  114.         dist[i][0] = 1e9;
  115.         depth[i] = 0;
  116.         dfs(i, i);
  117.     }
  118.     for (int j = 1; j < LOG; ++j) {
  119.         for (int i = 0; i < n; ++i) {
  120.             up[i][j] = up[up[i][j - 1]][j - 1];
  121.             dist[i][j] = min(dist[i][j - 1], dist[up[i][j - 1]][j - 1]);
  122.         }
  123.     }
  124. }
  125.  
  126. int kthancestor(int u, int k) {
  127.     int ret = 1e9;
  128.     for (int i = 0; i < LOG; ++i) {
  129.         if ((1 << i) & k) {
  130.             ret = min(ret, dist[u][i]);
  131.             u = up[u][i];
  132.         }
  133.     }
  134.     return ret;
  135. }
  136.  
  137. struct edge {
  138.     int u, v, w;
  139. };
  140.  
  141. void solve() {
  142.     int m;
  143.     cin >> n >> m;
  144.     vector<edge> e;
  145.     for (int i = 0; i < m; ++i) {
  146.         int u, v, w;
  147.         cin >> u >> v >> w;
  148.         u--, v--;
  149.         e.push_back({u, v, w});
  150.     }
  151.  
  152.     sort(all(e), [&](edge &a, edge &b) {
  153.         return a.w > b.w;
  154.     });
  155.  
  156.     DSU dsu(n);
  157.  
  158.     for (int i = 0; i < m; ++i) {
  159.         if(dsu.find(e[i].u) != dsu.find(e[i].v)) {
  160.             adj[e[i].u].emplace_back(e[i].v, e[i].w);
  161.             adj[e[i].v].emplace_back(e[i].u, e[i].w);
  162.             dsu.join(e[i].u, e[i].v);
  163.         }
  164.     }
  165.  
  166.     build();
  167.  
  168.     int q;
  169.     cin >> q;
  170.     while (q --) {
  171.         int u, v;
  172.         cin >> u >> v;
  173.         u--, v--;
  174.         if(!dsu.same(u, v)) {
  175.             cout << 0 << endl;
  176.             continue;
  177.         }
  178.         int lc = get_lca(u, v);
  179.         cout << min(kthancestor(u, depth[u] - depth[lc]),
  180.                     kthancestor(v, depth[v] - depth[lc])) << endl;
  181.     }
  182. }
  183.  
  184. signed main() {
  185.     Drakon();
  186.     int t = 1;
  187.     //cin >> t;
  188.     while (t--) {
  189.         solve();
  190.     }
  191. }
Success #stdin #stdout 0.01s 27716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/scLSqi
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!