FJ2016集训 day5
打了个酱油，身败名裂0。0
1 冷战
1.1 题目大意
给定一副 N 个点的图。动态的往图中加边，并且询问某两个点最早什么时候联通。
1.2 题解
考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并，这棵树的深度是 O(log n) 的。我们将一个点连向其父亲的边权设为这条边加入的时间，那么每次询问时，暴力查询树上从 u 到 v 所经过边权的最大值即可。时间复杂度为 O(n log n)，常数较小。假如写了常数较大的可以得到 80 分。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,id,cnt; int fa[500005],w[500005],dep[500005]; int find(int x) { return fa[x]?find(fa[x]):x; } void add(int u,int v) { int p=find(u),q=find(v); if(p==q)return; if(dep[p]>dep[q])swap(p,q); fa[p]=q;w[p]=id; if(dep[p]==dep[q])dep[q]++; } int query(int a,int b) { int ans=0; if(find(a)!=find(b))return 0; while(a!=b) { if(dep[a]>dep[b])ans=max(ans,w[b]),b=fa[b]; else ans=max(ans,w[a]),a=fa[a]; } return ans; } int main() { freopen("coldwar.in","r",stdin); freopen("coldwar.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++)dep[i]=1; int ans=0; for(int i=1;i<=m;i++) { int f=read(),u=read(),v=read(); u^=ans,v^=ans; if(f==0) { id++; add(u,v); } else { ans=query(u,v); printf("%d\n",ans); } } return 0; } |
计数器 9773975
OI 课件=>
OI 课件=>
强制在线啊QwQ 那我只会LCT QwQ
会被卡2333
明明 明明复杂度都是一样的!
orz hzwer，今天终于看到您了。后两题没看见多组数据成功爆成100的傻逼路过。