水灾

C++14(g++5.4) 解法, 执行用时: 1899ms, 内存消耗: 157236K, 提交时间: 2020-04-28 17:19:17

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e6+5;
typedef long long ll;
struct node
{
    int u,v,w;
    bool operator<(const node&o)const
    {
        return w>o.w;
    }
}e[N];
int n,m,q,k,f[N],dfn[N],id,fa[N][30],dep[N],lg[N],w[N],a[N],tot,head[N],nex[N<<1],to[N<<1];
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
void dfs(int u,int p)
{
    dfn[u]=++id;
    fa[u][0]=p;dep[u]=dep[p]+1;
    for(int i=1;1<<i<=dep[p];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=nex[i])
        dfs(to[i],u);
}
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;
    for(int i=lg[dep[u]];i>=0;i--)
        if(fa[u][i]!=fa[v][i])
        u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
bool cmp(int x,int y){return dfn[y]>dfn[x];}
int solve()
{
    sort(a+1,a+1+k,cmp);
    int ans=0;
    for(int i=2;i<=k;i++) ans=max(ans,w[LCA(a[i],a[i-1])]);
    return ans;
}
int main()
{
    for(int i=1;i<N;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<N;i++) lg[i]--;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+1+m);
    for(int i=1;i<=n+n-1;i++) f[i]=i;
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        int fu=getf(e[i].u),fv=getf(e[i].v);
        if(fu==fv) continue;
        sum++;
        w[++n]=e[i].w;
        add(n,fu);add(n,fv);
        f[fu]=f[fv]=n;
    }
    dfs(n,0);
    int lastans=0;
    while(q--)
    {
        scanf("%d",&k);
        for(int i=1;i<=k;i++) scanf("%d",&a[i]),a[i]^=lastans;
        if(k==1) printf("%d\n",lastans=0);
        else printf("%d\n",lastans=solve());
    }
}

C++ 解法, 执行用时: 1540ms, 内存消耗: 114288K, 提交时间: 2022-02-08 13:19:26

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
struct edge{
	int u,v,w;
}e[N];
int n,m,q,now,la,num,c,t[N],a[N],fa[N],v[N],nex[N],head[N],ki,ans;
bool cmp(edge x,edge y){return x.w>y.w;}
void add(int x,int y){
	nex[++now]=head[x];
	head[x]=now,v[now]=y;
}
int find(int x){
	return fa[x]?fa[x]=find(fa[x]):x;
}
int dfn[N],d[N],f[N][20];
void dfs(int x){
	d[x]=d[f[x][0]]+1,dfn[x]=++num;
	for(int i=1;i<20;i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i])
		f[v[i]][0]=x,dfs(v[i]);
}
int lca(int u,int v){
	if(d[u]>d[v])swap(u,v);
	for(int i=0;i<20;i++)
		if((d[v]-d[u])>>i&1)v=f[v][i];
	if(v==u)return v;
	for(int i=19;i>=0;i--)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	return f[u][0];
}
bool cmp1(int x,int y){
	return dfn[x]<dfn[y];
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;++i)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+m+1,cmp);c=n;
	for(int i=1;i<=m;++i){
		int f1=find(e[i].u),f2=find(e[i].v);
		if(f1!=f2){
			t[++c]=e[i].w,fa[f1]=fa[f2]=c;
			add(c,f1),add(c,f2);
		}
	}
	for(dfs(c);q--;){
		scanf("%d",&ki);
		for(int i=1;i<=ki;++i)scanf("%d",&a[i]),a[i]^=la;
		sort(a+1,a+ki+1,cmp1);
		ans=0;
		for(int i=1;i<ki;++i)
			ans=max(ans,t[lca(a[i],a[i+1])]);
		la=ans;
		printf("%d\n",ans);
	}
}

详情