fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 5e4 + 5, MAXM = 1e5 + 5, MAXL = 16;
  8. typedef pair<int, int> pii;
  9.  
  10. #define mp make_pair
  11. #define u first
  12. #define w second
  13.  
  14. struct edge{
  15.   int u, v, w;
  16.   bool operator<(const edge &rhs) const{
  17.     return w < rhs.w;
  18.   }
  19. } E[MAXM];
  20.  
  21. int T, N, M, Q, t = 1, L[MAXN], dp[MAXN][MAXL], MAX[MAXN][MAXL], p[MAXN], h[MAXN];
  22. vector<pii> adj[MAXN];
  23.  
  24. int find(int u){
  25.   if(p[u] == u) return u;
  26.   return p[u] = find(p[u]);
  27. }
  28.  
  29. void unite(int u, int v){
  30.   if(h[u] > h[v]) p[v] = u;
  31.   else if(h[v] > h[u]) p[u] = v;
  32.   else p[v] = u, h[u]++;
  33. }
  34.  
  35. void build(int u, int p){
  36.   for(int i=0; i<adj[u].size(); ++i){
  37.     int v = adj[u][i].u, w = adj[u][i].w;
  38.     if(v != p){
  39.       L[v] = L[u] + 1, dp[v][0] = u, MAX[v][0] = w;
  40.       build(v, u);
  41.     }
  42.   }
  43. }
  44.  
  45. int query(int u, int v){
  46.   if(L[u] < L[v]) swap(u, v);
  47.   int log = 1, resu = 0, resv = 0;
  48.   for(; (1<<log)<=L[u]; ++log);
  49.   log--;
  50.   for(int i=log; i>=0; --i)
  51.     if(L[u] - (1<<i) >= L[v]){ resu = max(resu, MAX[u][i]); u = dp[u][i]; }
  52.   if(u == v) return resu;
  53.   for(int i=log; i>=0; --i)
  54.     if(dp[u][i] != dp[v][i] && dp[u][i] != -1){
  55.       resu = max(resu, MAX[u][i]), resv = max(resv, MAX[v][i]);
  56.       u = dp[u][i], v = dp[v][i];
  57.     }
  58.   return max(max(resu, MAX[u][0]), max(resv, MAX[v][0]));
  59. }
  60.  
  61. int main(){
  62.   scanf("%d", &T);
  63.   while(T--){
  64.     int u, v, w;
  65.     scanf("%d %d", &N, &M);
  66.     for(int i=1; i<=M; ++i){ scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].w); E[i].u--, E[i].v--; }
  67.     sort(E + 1, E + M + 1);
  68.     for(int i=0; i<N; ++i){
  69.       adj[i].clear();
  70.       L[i] = 0, p[i] = i, h[i] = 0;
  71.       for(int j=0; (1<<j)<N; ++j) dp[i][j] = MAX[i][j] = -1;
  72.     }
  73.     for(int i=1; i<=M; ++i){
  74.       u = find(E[i].u), v = find(E[i].v), w = E[i].w;
  75.       if(u == v) continue;
  76.       unite(u, v);
  77.       u = E[i].u, v = E[i].v;
  78.       adj[u].push_back(mp(v, w));
  79.       adj[v].push_back(mp(u, w));
  80.     }
  81.     build(0, -1);
  82.     for(int j=1; (1<<j)<N; ++j)
  83.       for(int i=0; i<N; ++i)
  84.         if(dp[i][j - 1] != -1){
  85.           dp[i][j] = dp[dp[i][j - 1]][j - 1], MAX[i][j] = max(MAX[i][j - 1], MAX[dp[i][j - 1]][j - 1]);
  86.         }
  87.     scanf("%d", &Q);
  88.     printf("Case %d:\n", t++);
  89.     while(Q--){
  90.       scanf("%d %d", &u, &v);
  91.       printf("%d\n", query(u - 1, v - 1));
  92.     }
  93.   }
  94.   return 0;
  95. }
Success #stdin #stdout 0s 12064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XLBPiN
language:
C++14 (gcc 8.3)
created:
7 years 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!