【NOI 2018】归程 / 题解

【NOI 2018】归程 / 题解

题目背景

本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图(节点的编号从 1 至 n)。

我们依次用 l, a 描述一条边的长度、海拔。

作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。

我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。

题目描述

Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。

Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q 天,每一天 Yazid 都会告诉你他的出发点 v ,以及当天的水位线 p。

每一天,Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

需要特殊说明的是,第二天车会被重置,这意味着:

  • 车会在新的出发点被准备好。
  • Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

输入和输出

从文件 return.in 中读入数据。

单个测试点中包含多组数据。输入的第一行为一个非负整数 T,表示数据的组数。

接下来依次描述每组数据,对于每组数据:

  1. 第一行 2 个非负整数 n, m,分别表示节点数、边数。
  2. 接下来 m 行,每行 4 个正整数 u, v, l, a,描述一条连接节点 u, v 的、长度为 l、海拔为 a 的边。
    • 在这里,我们保证 1 ≤ u, v ≤ n。

接下来一行 3 个非负数 Q, K, S,其中 Q 表示总天数,K ∈ {0, 1} 是一个会在下面被用到的系数,S 表示的是可能的最高水位线。

接下来 Q 行依次描述每天的状况。每行 2 个整数 v_0, p_0 描述一天:

    • 这一天的出发节点为 $v = (v_0 + K × lastans − 1) \mod n + 1$。
    • 这一天的水位线为 $p = (p_0 + K × lastans) \mod (S + 1)$。
    • 其中 $lastans$ 表示上一天的答案(最小步行总路程)。特别地,我们规定第 1天时 $lastans = 0$。
  • 在这里,我们保证 $1 ≤ v_0 ≤ n$,$0 ≤ p_0 ≤ S$。

对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开。

依次输出各组数据的答案。对于每组数据:

  • 输出 Q 行每行一个整数,依次表示每天的最小步行总路程。

样例

输入

1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

输出

0
50
200
50
150

数据范围和提示

思路

实际上比赛的时候我是想出了正解的(但是我没打完 + 打萎了)。

首先我们发现前11个点都是送分的,尤其是前6个,最短路跑一遍就好了,体现出这是一道签到题。对于一条链。。。$O(n^2)$打打暴力也是可以的,一棵数也就是倍增一下就好了。

正解也很容易想到,把没有积水开车可以相互抵达的点并查集合并,同时维护一个“联通块”里走路到终点的最短路径。题目要求在线,那就用可持久化并查集。

代码

#include 
#define mid ((l+r)>>1)
#define maxn 400010
#define minn(a,b) a<b?a:b #define="" maxx(a,b)="" a="">b?a:b 
using namespace std;
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template  inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
int root[maxn],head[maxn],dis[maxn],n,m,cnt,cnt_e;
struct Edge{
    int to,next,val,lev;
    Edge(int a=0,int b=0,int c=0,int d=0){
        to=a,next=b,val=c,lev=d;
    }
}l[maxn<<2];
struct Sp_Edge{
    int from,to,lev;
    Sp_Edge(int a=0,int b=0,int c=0){
        from=a,to=b,lev=c;
    }
    bool operator < (const Sp_Edge &x) const{
        return lev>x.lev;
    }
}e[maxn<<2];
struct Node{
    int f,p,d;
    Node(int a=0,int b=0,int c=0){
        f=a,p=b,d=c;
    }
};
struct PT{
    int ls[maxn*44],rs[maxn*44],now;
    Node tree[maxn*44],ins;
    void ctl(int f,int p,int d){
        ins=Node(f,p,d);
    }
    inline int build(int l,int r){
        int o=++now;
        if (l==r){
            tree[o]=Node(l,1,dis[l]);
            return o;
        }
        ls[o]=build(l,mid);
        rs[o]=build(mid+1,r);
        return o;
    }
    inline int insert(int pre,int l,int r,int x){
        int o=++now;
        tree[o]=tree[pre];
        ls[o]=ls[pre],rs[o]=rs[pre];
        if (l==r){
            tree[o]=ins;
            return o;
        }
        if (x<=mid) ls[o]=insert(ls[pre],l,mid,x);
            else rs[o]=insert(rs[pre],mid+1,r,x);
        return o;
    }
    inline Node query(int o,int l,int r,int x){
        if (l==r) return tree[o];
        if (x<=mid) return query(ls[o],l,mid,x);
        else return query(rs[o],mid+1,r,x);
    }
    inline void reset(){
        memset(ls,0,sizeof(ls));
        memset(rs,0,sizeof(rs));
        memset(tree,0,sizeof(tree));
        now=0;
    }
}ds;
struct d_node{
    int v,d;
    d_node(int a=0,int b=0){
        v=a,d=b;
    }
    bool operator < (const d_node &x) const{
        return d>x.d;
    }
};
inline void Dijkstra(){
    int vis[maxn];
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queueq;
    q.push((d_node){1,0});
    dis[1]=0;
    while(!q.empty()){
        d_node hq=q.top();q.pop();
        if (vis[hq.v]) continue;
        vis[hq.v]=1;
        for (register int i=head[hq.v];i;i=l[i].next){
            int v=l[i].to;if (vis[v]) continue;
            if (dis[v]>dis[hq.v]+l[i].val)
            dis[v]=dis[hq.v]+l[i].val,q.push((d_node){v,dis[v]});
        }
    }
}
inline void Add(int fr,int to,int dis,int lev){
    l[++cnt]=Edge(to,head[fr],dis,lev);
    head[fr]=cnt;
    l[++cnt]=Edge(fr,head[to],dis,lev);
    head[to]=cnt;
    e[++cnt_e]=Sp_Edge(fr,to,lev);
}
inline int search(int x){
    int l=1,r=m,res=0;
    while(l<=r){
        if (e[mid].lev>x)
            res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}
inline int find(int now,int x){
    Node tem=ds.query(root[now],1,n,x);
    int fx=tem.f;
    if (fx==x) return x;
    return find(now,fx);
}
inline void merge(int now,int x,int y){
    int fx=find(now,x),fy=find(now,y);
    if (fx==fy) return;
    Node infx=ds.query(root[now],1,n,fx);
    Node infy=ds.query(root[now],1,n,fy);
    if (infx.p>=infy.p) swap(infx,infy),swap(fx,fy);
    ds.ctl(fy,infx.p,infx.d);
    root[now]=ds.insert(root[now],1,n,fx);
    ds.ctl(infy.f,maxx(infx.p+1,infy.p),minn(infx.d,infy.d));
    root[now]=ds.insert(root[now],1,n,fy);
}
inline void Solve(){
    io>>n>>m;
    int x,y,z,w,v0,p0;
    for (register int i=1;i<=m;i++){
        io>>x>>y>>z>>w;
        Add(x,y,z,w);
    }
    Dijkstra();
    sort(e+1,e+1+m);
    root[0]=ds.build(1,n);
    for (register int i=1;i<=m;i++){
        root[i]=root[i-1];
        merge(i,e[i].from,e[i].to);
    }
    int q,k,s,lastans=0;
    io>>q>>k>>s;
    for (register int i=1;i<=q;i++){
        io>>v0>>p0;
        v0=(v0+k*lastans-1)%n+1;
        p0=(p0+k*lastans)%(s+1);
        int pos=search(p0);
        int loc=find(pos,v0);
        Node tem=ds.query(root[pos],1,n,loc);
        lastans=tem.d;
        printf("%dn",lastans);
    }
}
inline void Reset(){
    memset(root,0,sizeof(root));
    memset(head,0,sizeof(head));
    memset(l,0,sizeof(l));
    memset(e,0,sizeof(e));
    n=0,m=0,cnt=0,cnt_e=0;
    ds.reset();
}
int main(){
    int T;
    io>>T;
    for (int i=1;i<=T;i++){
        Solve();
        if (i==T) break;
        Reset();
    }
    return 0;
}</b?a:b>
Show Comments