萌新刚学 KRUSKAL 重构树 0.114514s 求调。
查看原帖
萌新刚学 KRUSKAL 重构树 0.114514s 求调。
1296826
lcfollower楼主2025/6/17 19:16

rt。。。

样例第二组数据 WA 了。

# include <bits/stdc++.h>

# define int long long
# define up(i ,x ,y) for (int i = x ; i <= y ; i ++)
# define dn(i ,x ,y) for (int i = x ; i >= y ; i --)
# define inf 1e14
 
using namespace std;
 
inline int read (){int s = 0 ; bool w = 0 ; char c = getchar () ; while (!isdigit (c)) {w |= (c == '-') ,c = getchar () ;} while (isdigit (c)){s = (s << 1) + (s << 3) + (c ^ 48) ; c = getchar ();}return w ? -s : s;}
inline void write (int x){if (x < 0) putchar ('-') ,x = -x; if (x > 9) write (x / 10) ; putchar (x % 10 | 48);}
inline void writesp (int x){write (x) ,putchar (' ');}
inline void writeln (int x){write (x) ,putchar ('\n');}

const int N = 2e4 + 10 ,M = N;
int n ,m ,cnt1 ,fa[N] ,val[N] ,lg[N] ,dep[N] ,Fa[N][21];
bool vis[N];
int st[N][21];
int cnt ,head[N];
struct E {int u ,v ,w;}graph[M << 1];
inline void add (int u ,int v ,int w) {
  graph[++ cnt] = {u ,v ,w};  
} inline bool cmp (E x ,E y) {return x.w > y.w;}
inline int find (int x) {return x == fa[x] ? x : fa[x] = find (fa[x]);}
struct EDGE {int to ,nxt;}edge[M << 1];
inline void add1 (int u ,int v){
  edge[++ cnt1] = {v ,head[u]} ,head[u] = cnt1;
}
# define fa Fa
inline void dfs (int u ,int fath){
  vis[u] = 1;
  dep[u] = dep[fath] + 1 ,fa[u][0] = fath;
  up (i ,1 ,20) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int i = head[u] ; i ; i = edge[i].nxt){
    int v = edge[i].to;
    if (v == fath) continue;
    dfs (v ,u);
  }
} inline int LCA (int u ,int v){
  if (dep[u] < dep[v]) swap (u ,v);
  while (dep[u] > dep[v]) u = fa[u][lg[dep[u] - dep[v]]];
  if (u == v) return u;
  dn (i ,20 ,0) if (fa[u][i] ^ fa[v][i]) u = fa[u][i] ,v = fa[v][i];
  return fa[u][0];
}
# undef fa
inline void init (){
  lg[0] = -1;
  up (i ,1 ,N - 10) lg[i] = lg[i >> 1] + 1;
  up (i ,1 ,n) if (!vis[find (i)]) dfs (find (i) ,0);
  up (i ,1 ,n - 1) st[i][0] = val[LCA (i ,i + 1)];
  up (j ,1 ,20)
    for (int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
      st[i][j] = max (st[i][j - 1] ,st[i + (1 << (j - 1))][j - 1]);
  
} inline int query (int l ,int r) {
  int k = lg[r - l + 1];
  return max (st[l][k] ,st[r - (1 << k) + 1][k]);
} inline void solve (){
  n = read () ,m = read ();int Q = read () ;
  cnt = cnt1 = 0;
  memset (vis ,0 ,sizeof vis);
  memset (Fa ,0 ,sizeof Fa);
  memset (head ,0 ,sizeof head);
  memset (st ,0 ,sizeof st);
  up (i ,1 ,n << 1) fa[i] = i;
  up (i ,1 ,m) {
    int u = read () ,v = read ();
    add (u ,v ,i) ,add (v ,u ,i);
  } sort (graph + 1 ,graph + 1 + cnt ,cmp);
  int e = n - 1 ,id = n;
  up (i ,1 ,cnt) {
    int fx = find (graph[i].u) ,fy = find (graph[i].v);
    if (fx ^ fy) {
      val[++ id] = graph[i].w;
      fa[fx] = fa[fy] = fa[id] = id;
      add1 (id ,fx) ,add1 (id ,fy) ,add1 (fx ,id) ,add1 (fy ,id);
      -- e;
      if (!e) break;
    }
  } n = id;
  init ();
  while (Q --) {
    int l = read () ,r = read ();
    if (l == r) writesp (0);
    else writesp (query (l ,r - 1));
  } puts ("");
} signed main (){
  int T = read ();
  while (T --) solve ();
  return 0 ;
}
2025/6/17 19:16
加载中...