[USACO24FEB] Infinite Adventure P

· · 题解

很深刻的题。

图上行走问题自然想到倍增，先简单尝试一下。

记 f_{i,j,k} 表示日期 \bmod T_i=k，从 i 走 2^j 步到的节点。

但发现走 2^j 步的过程中，可能走到 T_u\gt T_i 的点，这样只记录日期 \bmod T_i 的信息就不够了。

所以如果遇到了点 u，我们将 f_{i,j,k} 强制停止在点 u，需要记录 g_{i,j,k} 表示实际行走的长度。

我们称 T_i 相同的点为同一层的点，考虑这样对于每次询问的复杂度，每一步有 2 种可能，如果强制停止了，那么层数加 1，否则剩余距离减半。

记 m=\max T_i,N=\sum T_i，每次减半前最多爬 \log m 层，一次询问的复杂度为 O(\log m\log V)。

但是我们预处理时同样要这样走，所以总时间复杂度为 O(N\log^2 V\log m)，无法通过。

发现实际上我们记录这个 2^j 步并没有什么意义，因为我们可能根本走不到 2^j 步就强制停止了，而这个步数的要求却使得我们有较高的复杂度。

因为只有走到了，T_u\gt T_i 的点 u 才会强制停止，我们干脆把 f_{i,j,k} 定义为，从 i 走 2^j 个同一层的点后到达的点，这里同样会强制停止，但是我们的预处理的复杂度变成 O(N(\log m+\log V))。

再来考虑询问，我们先用 O(\log m) 的复杂度爬到最高层，再用 O(\log V) 的复杂度找到这一层的最后一个节点，然后层数上限减 1，总复杂度 O(\log m(\log m+log V))。

这样，我们以 O(N(\log m+\log V)+Q\log m(\log m+log V)) 的复杂度解决了本题。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=2e18;
const int N=1e5+5;
int n,q,t[N],mx;
int *c[N],*f[61][N];
ll *g[61][N];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i){
        scanf("%d",&t[i]);
        c[i]=new int[t[i]];
        mx=max(mx,t[i]);
        for(int j=0;j<=60;++j)f[j][i]=new int[t[i]],g[j][i]=new ll[t[i]];
    }
    for(int i=1;i<=n;++i)
        for(int j=0;j<t[i];++j)scanf("%d",&c[i][j]);
    for(int j=1;j<=mx;j<<=1){
        for(int i=1;i<=n;++i)if(t[i]==j)for(int k=0;k<j;++k){
            int x=c[i][k];ll dt=1;
            while(t[x]<j&&dt<inf){
                int y=f[60][x][k+dt&t[x]-1];
                dt+=g[60][x][k+dt&t[x]-1];
                x=y;
            }
            f[0][i][k]=x,g[0][i][k]=min(inf,dt);
        }
        for(int l=1;l<=60;++l)for(int i=1;i<=n;++i)if(t[i]==j)for(int k=0;k<j;++k){
            int x=f[l-1][i][k];ll dt=g[l-1][i][k];
            if(t[x]!=j){
                f[l][i][k]=x;
                g[l][i][k]=dt;
                continue;
            }
            f[l][i][k]=f[l-1][x][k+dt&j-1];
            g[l][i][k]=min(inf,g[l-1][x][k+dt&j-1]+dt);
        }
    }
    while(q--){
        int x;ll T,dt,w;
        scanf("%d%lld%lld",&x,&T,&dt);
        while(dt){
            for(int j=60;~j&&dt;--j)if((w=g[j][x][T&t[x]-1])<=dt){
                dt-=w;
                int ls=t[x];
                x=f[j][x][T&t[x]-1];
                T+=w;
                if(t[x]!=ls)j=61;
            }
            if(dt){
                x=c[x][T&t[x]-1];
                ++T,--dt;
            }
        }
        printf("%d\n",x);
    }
    return 0;
}