[JZOJ 5782] 城市猎人

[JZOJ 5782] 城市猎人

思路：
并查集按秩合并维护出现时间。
最早连接时间就是树上连接最大值。
(qwq)我居然把路径压缩和按秩合并打到一个程序里了...OvO

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
struct edge {int to;int nxt;int w;
}e[maxn << 1];//struct asks{
//  int x,y;
//}q[maxn<<1];int n,m,q,cnt;
int x,y;
int rank[maxn];
int fa[maxn];
int head[maxn];inline int find(int x) {return x == fa[x] ? x : find(fa[x]);
} inline void Add_edge(int u,int v,int w) {e[++cnt].w = w;if(rank[u] > rank[v]) {fa[v] = u;e[cnt].to = u;e[cnt].nxt = head[v];head[v] = cnt;}else {fa[u] = v;e[cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt;if(rank[u] == rank[v]) rank[u] ++;}return;
}inline int query(int x,int y) {int dx = 0;int dy = 0;int res = 0;int l = x;int r = y;while(fa[l] != l) {l = fa[l];dx++;}while(fa[r] != r) {r = fa[r];dy ++;}if(dx < dy) {swap(dx,dy);swap(x,y);}while(dx > dy) {res = max(e[head[x]].w,res);x = fa[x];dx --;}if(x == y) return res;while(x != y) {res = max(res,max(e[head[x]].w,e[head[y]].w));x = fa[x];y = fa[y];}return res;
}int main () {#ifdef ONLINE_JUDGEfreopen("pictionary.in","r",stdin);freopen("pictionary.out","w",stdout);#endifscanf("%d %d %d",&n,&m,&q);for(int i = 1;i <= n; ++i) {fa[i] = i;}for(int i = 1;i <= m; ++i){int d = m - i + 1;for(int j = d*2;j <= n;j += d) {Add_edge(find(d),find(j),i);//cout<<d << ' '<< j<<endl;}}for(int i = 1;i <= q; ++i) {scanf("%d %d",&x,&y);printf("%dn",query(x,y));}return 0;}

转载于:.html