洛谷P4768/NOI2018 归程

@Pelom  October 30, 2019

题意

数据范围:$n \le 200000,m \le 400000,q \le 400000$ [强制在线]

题解

分析题意:需要找到一个节点$u$,使得从起点$v \rightarrow u$上的所有节点的海拔$> p$,并且使得从$u \rightarrow 1$距离最小
第一个要求可以用$\mathrm{Kruskal}$重构树解决(以海拔为关键字降序建立);因为重构树是小根堆,所以每个节点子树内所有节点海拔都比该节点大;因此对于每次询问,找到重构树中深度最小且海拔大于水位的节点(可用树上倍增解决),该节点的子树皆满足第一个要求
对于第二个要求,因为树的形态不变,可用$\mathrm{Dijkstra}$与$\mathrm{dfs}$预处理出每一个节点的子树中到$1$节点距离的最小值

注:

  • 可在重构树的同时维护子树信息(即不用$\mathrm{dfs}$)

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define mp make_pair
typedef long long LL;
typedef pair<LL,int> pli;
const int N=400000+10;
int t,n,m,u,v,l,a,q,k,s,p;
int cnt,tot;
int head[N],f[N],val[N],fa[N][23];
LL dis[N],mi[N];
priority_queue<pli,vector<pli>,greater<pli> > pq;
struct Edge{
    int u,v,w;
    inline bool operator < (const Edge& x) const{
        return w>x.w;
    }
} E[N];
struct edge{
    int nxt,to,w;
} e[N<<2];
inline void add(int u,int v,int w=0){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
inline void Dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    pq.push(mp(0,1));
    dis[1]=0;
    for(;!pq.empty();){
        LL d=pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if(d!=dis[u])
            continue;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>d+e[i].w){
                dis[v]=d+e[i].w;
                pq.push(mp(dis[v],v));
            }
        }
    }
}
void dfs(int u){
    mi[u]=dis[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        fa[v][0]=u;
        dfs(v);
        mi[u]=min(mi[u],mi[v]);
    }
}
inline void Kruskal(){
    tot=n;
    sort(E+1,E+m+1);
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        int fu=find(E[i].u),fv=find(E[i].v);
        if(fu==fv)
            continue;
        val[++tot]=E[i].w;
        f[tot]=f[fu]=f[fv]=tot;
        add(tot,fu);
        add(tot,fv);
    }
    dfs(tot);
}
int main(){
    scanf("%d",&t);
    for(;t--;){
        memset(head,0,sizeof(head));
        memset(fa,0,sizeof(fa));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d%d",&u,&v,&l,&a);
            E[i].u=u,E[i].v=v,E[i].w=a;
            add(u,v,l);
            add(v,u,l);
        }
        Dijkstra();
        cnt=0;
        memset(head,0,sizeof(head));
        Kruskal();
        for(int i=1;(1<<i)<=tot;i++)
            for(int u=1;u<=tot;u++)
                fa[u][i]=fa[fa[u][i-1]][i-1];
        scanf("%d%d%d",&q,&k,&s);
        LL lst=0;
        for(;q--;){
            scanf("%d%d",&v,&p);
            v=(v+k*lst-1)%n+1;
            p=(p+k*lst)%(s+1);
            for(int i=22;~i;i--)
                if(fa[v][i] && val[fa[v][i]]>p)
                    v=fa[v][i];
            lst=mi[v];
            printf("%lld\n",lst);
        }
    }
    return 0;
}

添加新评论