[noi2018] return (Kruskal reconstruction tree / persistent and search set)

Rogue portal

Title Description

Given a n A little bit m Undirected graph of strip and edge , Each side has height and length ,Q Time to ask , Each given starting point , And limit height , Find the point that can be reached from the starting point through the edge whose height is greater than the limit height , To 1 The minimum value of the shortest circuit at point
Forced Online

65pts Don't force online

Sort the edge weight and the weight of inquiry , Maintain the connected block with the union search set 1 The point with the smallest distance

100pts

Solution 1

stay 65pts Improve on
We just need to make the process of merging with union search set persistent , You can access any version of the search set
You can be online
If we use rank merged union search set $O(nlo{g}^{2}n)$

Solution 2

Build out Kruskal Refactoring tree
Then the reachable point is a subtree , The farthest you can get to that point with tree doubling maintenance
Preprocess the subtree of each point to 1 The nearest point from store No. 1 is enough
The time complexity is zero $O(nlogn)$, And there are few details , Small space consumption

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+3;
struct P
{
    
	int id;
	LL v;
};
bool operator <(const P &x,const P &y)
{
    
	return x.v>y.v;
}
priority_queue<P> q;
struct node
{
    
	int y,next,l;
}e[4*N];
struct edge
{
    
	int x,y,h;
}E[2*N]; 
int link[N],t;
int n,m,Q,K,s;
void Insert(int x,int y,int l)
{
    
	e[++t].y=y;
	e[t].l=l;
	e[t].next=link[x];
	link[x]=t;
}
bool cmp(edge a,edge b)
{
    
	return a.h>b.h;
}
int read(){
    
	int ans=0,op=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
    if(ch=='-') op=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
    ans=(ans<<1)+(ans<<3)+ch-'0';ch=getchar();}
	return ans*op;
}
bool vis[N];
LL dis[N];
P Pc(int x,LL v)
{
    
	P tem;
	tem.id=x;
	tem.v=v;
	return tem; 
} 
void dijistra()
{
    
	for(int i=1;i<=n;i++)
	{
    
		vis[i]=0;
		dis[i]=1e15;
	}
	dis[1]=0;
	q.push(Pc(1,0));
	while(!q.empty())
	{
    
		P tp=q.top();q.pop();
		int x=tp.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=link[x];i;i=e[i].next)
		{
    
			int y=e[i].y;
// cout<<x<<' '<<y<<' '<<dis[x]<<' '<<e[i].l<<' '<<dis[y]<<endl;
			if(dis[x]+e[i].l<dis[y])
			{
    
				dis[y]=dis[x]+e[i].l;
				q.push(Pc(y,dis[y])); 
			}
		}
	}
}	
int cnt,f[2*N],val[2*N],Min[2*N];
int Find(int x)
{
    
	if(x==f[x]) return x;
	return f[x]=Find(f[x]);
}
int up[2*N][30];
void kruskal()
{
    
	for(int i=1;i<=n;i++)
	{
    
		Min[i]=dis[i];	
		f[i]=i;
	}
	sort(E+1,E+m+1,cmp);
	memset(link,0,sizeof(link));
	t=0;
	for(int i=1;i<=m;i++)
	{
    
		int x=E[i].x;
		int y=E[i].y;
		int fx=Find(x),fy=Find(y);
		if(fx==fy) continue;
		cnt++;
		val[cnt]=E[i].h;
		Min[cnt]=min(Min[fx],Min[fy]);
		f[fx]=cnt;f[cnt]=cnt;f[fy]=cnt;
		up[fx][0]=cnt;
		up[fy][0]=cnt;
		Insert(cnt,fx,0);
		Insert(cnt,fy,0);
	}
}

int main()
{
    
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
    		
		t=0;

		memset(link,0,sizeof(link));
		memset(vis,0,sizeof(vis));
		memset(Min,89,sizeof(Min));
		memset(up,0,sizeof(up));
		n=read();m=read();		cnt=n;
		for(int i=1;i<=m;i++)
		{
    
			int x,y,l,h;
			x=read();
			y=read();
			l=read();
			h=read();
			Insert(x,y,l);
			Insert(y,x,l);
			E[i].x=x;
			E[i].y=y;
			E[i].h=h;
		}
		dijistra();
		kruskal();
		for(int k=1;(1<<k)<=cnt;k++) 
			for(int i=1;i<=cnt;i++) 
				up[i][k]=up[up[i][k-1]][k-1];
		Q=read();K=read();s=read();
		LL last=0;
		while(Q--)
		{
    
			int v0,h0;
			v0=read();
			h0=read();
			int v=(v0+K*last-1)%n+1;
			int h=(h0+K*last)%(s+1); 
			for(int k=22;k>=0;k--)
				if(up[v][k]&&val[up[v][k]]>h) 
					v=up[v][k];
			last=Min[v];
			printf("%lld\n",Min[v]);
		}		
	} 

	return 0;
}