旅行

C++11(clang++ 3.9) 解法, 执行用时: 4752ms, 内存消耗: 304828K, 提交时间: 2020-03-13 16:25:19

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
#define min(q,w) q>w?w:q
#define max(q,w) q<w?w:q;
using namespace std;
typedef long long LL;
const int N=500500,Hmo=19000003;
int read(int &n)
{
	char ch=' ';
	int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-') w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())
	q=q*10+ch-48;
	n=q*w;
	return n;
 } 
 void write(int x)
 {
 	if(x==0)
 	{
 		putchar('0');
 		return;
	 }
	 char s[12],l=0;
	 while(x!=0) s[++l]=x%10+48,x/=10;
	 fod(i,l,1) putchar(s[i]);
 }
 int m,n,m1,ans;
 bool z[N];
 int czx[N][3],cl[N];
 int B[2*N][2],A[N],B0;
 int Fa[N][20],dis[N][20];
 int Mdis[Hmo+10];
 LL Hx[Hmo+10];
 int HX(LL q)
 {
 	int i=q%Hmo;
 	for(;Hx[i]!=q&&Hx[i];)
 	if((++i)==Hmo) i=0;
 	return i;
 }
 void link(int q,int w)
 {
 	B[++B0][0]=A[q],A[q]=B0,B[B0][1]=w;
 	B[++B0][0]=A[w],A[w]=B0,B[B0][1]=q;
 }
 int Si[N];
 int ZX,ZX1;
 int dfsf(int q,int fa)
 {
 	Si[q]=1;
 	efo(i,q) if(!z[B[i][1]]&&B[i][1]!=fa) Si[q]+=dfsf(B[i][1],q);
 	return Si[q];
 }
 void dfss(int q,int fa,int Alln)
 {
 	int mx=0;
 	efo(i,q) if(!z[B[i][1]]&&B[i][1]!=fa) mx=max(mx,Si[B[i][1]]);
 	mx=max(mx,Alln-Si[q]);
 	if(mx<ZX1) ZX1=mx,ZX=q;
 	efo(i,q) if(!z[B[i][1]]&&B[i][1]!=fa) dfss(B[i][1],q,Alln);
 }
 void dfs(int q,int fa,int c,int FA,int C)
 {
 	dis[q][C]=c;
 	Fa[q][C]=FA;
 	efo(i,q) if(!z[B[i][1]]&&B[i][1]!=fa) dfs(B[i][1],q,c+1,FA,C);
 }
 void divide(int q,int C)
 {
 	int Alln=dfsf(q,0);
 	ZX1=1e9;
 	dfss(q,0,Alln);
 	z[q=ZX]=1;
 	dfs(q,0,0,q,C);
 	efo(i,q) if(!z[B[i][1]]) divide(B[i][1],C+1);
 }
 int main()
 {
 	int q,w;
 	read(n),read(m),read(m1);
 	fo(i,1,n-1) read(q),read(w),link(q,w);
 	int Ssi=0;
 	cl[0]=1;
 	fo(i,1,m)
 	{
 		Ssi+=read(q);
		 czx[i][0]=cl[0];
		 fo(j,1,q) read(cl[cl[0]]),++cl[0];
		 czx[i][1]=cl[0]-1; 
	 }
	 divide(1,0);
	 fo(I,1,m)
	 {
	 	fo(i,czx[I][0],czx[I][1])
	 	{
	 		w=cl[i];
	 		fo(j,0,19)
	 		{
	 			if(!Fa[w][j]) break;
	 			int t=HX((LL)I*(n+1)+Fa[w][j]);
	 			if(!Hx[t]) Hx[t]=(LL)I*(n+1)+Fa[w][j];
	 			Mdis[t]=max(Mdis[t],n-dis[w][j]);
			 }
		 }
	 }
	 ans=0;
	 fo(I,1,m1)
	 {
	 	read(q),read(w);
	 	q=(q+ans)%n+1,w=(w+ans)%m+1;
	 	ans=1e9;
	 	fo(i,0,19)
	 	{
	 		if(!Fa[q][i]) break;
	 		int t=HX((LL)w*(n+1)+Fa[q][i]);
	 		ans=min(ans,dis[q][i]+n-Mdis[t]);
		 }
		 write(ans);
		 putchar('\n');
	 }
	 return 0;
 }

C++14(g++5.4) 解法, 执行用时: 1059ms, 内存消耗: 263144K, 提交时间: 2019-03-15 21:40:25

#include<map>
#include<cstdio> 
#include<cstring>
#include<algorithm>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

const int N = 4e5 + 5;

void read(int &x) {
	#define gc getchar
	char c = ' '; x = 0;
	while(c < '0' || c > '9') c = gc();
	for(; c >= '0' && c <= '9'; c = gc()) x = x * 10 + c - '0';
}

int n, x, y, m, q, k;
int fi[N], nt[N * 2], to[N * 2], tot;

void link(int x, int y) {
	nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;
}

int siz[N], mx[N], G, bz[N];

void fg(int x) {
	bz[x] = 1;
	siz[x] = 1; mx[x] = 0;
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]])
		fg(to[i]), siz[x] += siz[to[i]],
		mx[x] = max(mx[x], siz[to[i]]);
	mx[x] = max(mx[x], siz[0] - siz[x]);
	if(mx[x] < mx[G]) G = x;
	bz[x] = 0;
}

int fa[N], dep[N], D;
int dis[20][N];

void dfs(int x) {
	bz[x] = 1;
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]]) {
		dis[D][to[i]] = dis[D][x] + 1;
		dfs(to[i]);
	}
	bz[x] = 0;
}

void dg(int x) {
	fg(x); dep[x] = dep[fa[x]] + 1;
	D = dep[x]; dfs(x);
	bz[x] = 1;
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]]){
		siz[0] = siz[to[i]]; G = 0; fg(to[i]);
		fa[G] = x; dg(G);
	}
}

const int M = 19260817;

ll num(int x, int y) { return (ll) (x - 1) * n + y;}
ll h[M]; int f[M];
int ha(ll n) {
	int y = n % M;
	while(h[y] != 0 && h[y] != n) y = (y + 1) % M;
	return y;
}

int ans;

int main() {
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	scanf("%d %d %d", &n, &m, &q);
	fo(i, 1, n - 1) {
		read(x); read(y);
		link(x, y); link(y, x);
	}
	siz[0] = mx[0] = n;
	fg(1); dg(G);
	fo(i, 1, m) {
		int k; read(k);
		fo(j, 1, k) {
			read(x);
			for(int p = x; p; p = fa[p]) {
				int D = dep[p];
				int u = ha(num(i, p));
				if(!h[u]) {
					h[u] = num(i, p);
					f[u] = dis[D][x];
				} else f[u] = min(f[u], dis[D][x]);
			}
		}
	}
	fo(i, 1, q) {
		read(x); read(y);
		x = (x + ans) % n + 1;
		y = (y + ans) % m + 1;
		ans = 1e9;
		for(int p = x; p; p = fa[p]) {
			int D = dep[p];
			int u = ha(num(y, p));
			if(h[u]) {
				ans = min(ans, f[u] + dis[D][x]);
			}
		}
		pp("%d\n", ans);
	}
}

详情