NOI2018-day1-归程(return)
相关题目:[NOI2018]归程

Solution

【题目背景】

       本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。        魔力之都可以抽象成一个 nn 个节点、 mm 条边的无向连通图(节点的编号从 11nn )。我们依次用 l,al,a 描述一条边的长度、海拔。        作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免 的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。        我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。

【题目描述】

       Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他 温暖的家。        Yazid 的家恰好在魔力之都的 11 号节点。对于接下来 QQ 天,每一天 Yazid 都会告诉你他的出发点 vv ,以及当天的水位线 pp 。        每一天,Yazid 在出发点都拥有一辆。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

  • 需要特殊说明的是,第二天车会被重置,这意味着:
    • 车会在新的出发点被准备好。
    • Yazid 不能利用之前在某处停放的车。

       Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。        本题的部分测试点将强制在线,具体细节请见【输入格式】和【子任务】

【输入格式】

       从 return.inreturn.in 中读入数据。        单个测试点中包含多组数据。输入的第一行为一个非负整数 TT ,表示数据的组数。接下来依次描述每组数据,对于每组数据:

  • 第一行 22 个非负整数 n,mn,m ,分别表示节点数、边数。
  • 接下来 mm 行,每行 44 个正整数 u,v,l,au, v, l, a ,描述一条连接节点 u,vu, v 的、长度为 ll 、海拔为 aa 的边。 在这里,我们保证 1u,vn1 \leq u,v \leq n
  • 接下来一行 33 个非负数 Q,K,SQ, K, S ,其中 QQ 表示总天数, K0,1K \in {0,1} 是一个会在下面被用到的系数, SS 表示的是可能的最高水位线。
  • 接下来 QQ 行依次描述每天的状况。每行 22 个整数 v0,p0v_0, p_0 描述一天:
    • 这一天的出发节点为
    • 这一天的水位线为
    • 其中 lastanslastans 表示上一天的答案(最小步行总路程)。特别地,我们规定第 11 天时 lastans=0lastans = 0
    • 在这里,我们保证 1v0n,0p0S1 \leq v_0 \leq n,0 \leq p_0 \leq S

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

【输出格式】

      输出到文件 return.outreturn.out 中。       依次输出各组数据的答案。对于每组数据:

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

【样例 1 输入】

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

【样例 1 输出】

0
50
200
50
150

【样例 1 解释】

       第一天没有降水,Yazid 可以坐车直接回到家中。        第二天、第三天、第四天的积水情况相同,均为连接 1,21, 2 号节点的边、连接 3,43, 4 号 点的边有积水。        对于第二天,Yazid 从 22 号点出发坐车只能去往3 号节点,对回家没有帮助。因此 Yazid 只能纯靠徒步回家。        对于第三天,从 44 号节点出发的唯一一条边是有积水的,车也就变得无用了。Yazid只能纯靠徒步回家。        对于第四天,Yazid 可以坐车先到达 22 号节点,再步行回家。 第五天所有的边都积水了,因此 Yazid 只能纯靠徒步回家。

【样例 2 输入】

1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0

【样例 2 输出】

0
2
3
1

【样例 2 解释】

       本组数据强制在线。        第一天的答案是 00,因此第二天的 v=(5+01) mod 5+1=5, p=(2+0) mod (3+1)=2v = (5 + 0 - 1)~ \text{mod}~ 5 + 1 = 5,~p = (2 + 0)~ \text{mod}~ (3 + 1) = 2。        第二天的答案是 22,因此第三天的 v=(2+21) mod 5+1=4, p=(0+2) mod (3+1)=2v = (2 + 2 - 1)~ \text{mod}~ 5 + 1 = 4,~p = (0 + 2)~ \text{mod}~ (3 + 1) = 2。        第三天的答案是 33,因此第四天的 v=(4+31) mod 5+1=2, p=(0+3) mod (3+1)=3v = (4 + 3 - 1)~ \text{mod}~ 5 + 1 = 2,~p = (0 + 3)~ \text{mod}~ (3 + 1) = 3

【子任务】

       所有测试点均保证 T3T \leq 3 ,所有测试点中的所有数据均满足如下限制:

  • n2×105n \leq 2 \times 10^5m4×105m \leq 4 \times 10^5Q4×105Q \leq 4 \times 10^5K0,1K \in {0,1}1S1091 \leq S \leq 10^9
  • 对于所有边: l104l \leq 10^4a109a \leq 10^9
  • 任意两点之间都直接或间接通过边相连。

为了方便你快速理解,我们在表格中使用了一些简单易懂的表述。在此,我们对这些内容作形式化的说明:

  • 图形态:对于表格中该项为“一棵树”或“一条链”的测试点,保证 m=n1m = n-1。 除此之外,这两类测试点分别满足如下限制:
    • 一棵树:保证输入的图是一棵树,即保证边不会构成回路。
    • 一条链:保证所有边满足 u+1=vu + 1 = v
  • 海拔:对于表格中该项为“一种”的测试点,保证对于所有边有 a=1a = 1
  • 强制在线:对于表格中该项为“是”的测试点,保证 如果该项为“否”, 则有 K=0K = 0
  • 对于所有测试点,如果上述对应项为“不保证”,则对该项内容不作任何保证。

为了优化你的阅读体验,我们在表格中把测试点的编号放在了中间,请注意这一点

Solution

预备知识:Kruskal重构树

首先我们预处理出每个点到 11 点的最短路径。 如果允许离线,我们可以按照海拔从大到小排序,逐个加入图中,每一个没有水的连通块的代价就是其到 11 点的最短路径的最小值。用并查集维护即可。

对于在线的情况,我们考虑Kruskal重构树,当并查集合并两个集合的时候,我们新建节点连接这两个集合。这样我们就可以把边权(海拔)转移到点上。因为我们是按海拔从大到小加边的,也就使得在重构树上的结点为最小海拔。

我们保证海拔 >T>T ,我们从 起点v0v_{0} 往上跳。然后只要维护一下联通块内的最小路径就好了,这个是可以与处理的。跳的时候可以用倍增优化。总复杂度:O((n+m) log n+Q log n)O((n+m)~log~n+Q~log~n)

Code

总时间:11090 ms/内存:59356 KiB   -O2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define pii pair<ll,int>
#define fi first
#define se second
const int N = 400002, M = 1000002;
typedef long long ll;
template <class T>inline void read(T &x) {
x=0; int f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
int cnt, nxt[M], head[N], to[M], w[M];
#define add(u,v,l) (nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=l)
#define add2(u,v) (nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v)
#define clear_Edge (memset(head,0,sizeof head),cnt=0)
#define travel(u) for(re i=head[u];i;i=nxt[i])
struct Edge {
int u, v, H;
inline bool operator < (const Edge &rhs)const{return H>rhs.H;}
} e[M];
int fa[N];
int find(int x){return !fa[x]?x:fa[x]=find(fa[x]);}

priority_queue<pii,vector<pii>,greater<pii> > q;
ll dis[N]; bool vis[N];
inline void Dijkstra() {
memset(vis, 0, sizeof vis); memset(dis, 0x7f, sizeof dis); dis[1]=0;
q.push(make_pair(0,1));
int v;
while(!q.empty()) {
pii u=q.top(); q.pop();
if(vis[u.se]) continue;
vis[u.se]=1;
travel(u.se) { v = to[i];
if(dis[v] > u.fi+w[i]) {
dis[v] = u.fi+w[i];
q.push(make_pair(dis[v],v));
}
}
}
}

int T, n, m, id, H[N], f[N][21];
ll d[N], lastans;
void dfs(int u) {
travel(u)
dfs(to[i]),f[to[i]][0]=u,d[u]=min(d[u],d[to[i]]);
if(u<=n) d[u]=dis[u];
}
inline void init() {rep(j,1,20)rep(i,1,id)f[i][j]=f[f[i][j-1]][j-1];}
inline void rec() {
clear_Edge; memset(fa,0,sizeof fa);
rep(i,1,m) {
int p=find(e[i].u), q=find(e[i].v);
if(p!=q) {
fa[p]=fa[q]=++id; // new Node
add2(id,p), add2(id,q); //Kruskal重构树
H[id] = e[i].H;
}
}
memset(d,0x7f,sizeof d); dfs(id); init();
}
int main() {
static int u, v, l, a, Q, K, S, p;
read(T);
while(T--) {
read(n), read(m); id=n; clear_Edge;
rep(i,1,m) {
read(u),read(v),read(l),read(a);
add(u,v,l); add(v,u,l); e[i]=(Edge){u,v,a};
}
sort(e+1, e+m+1);
Dijkstra(); rec();

read(Q), read(K), read(S); lastans=0;
while(Q--) {
read(v), read(p);
v = (v+K*lastans-1)%n+1;
p = (p+K*lastans)%(S+1);
for(int i=20;i>=0;--i) if(H[f[v][i]]>p)v=f[v][i];
printf("%lld\n", lastans=d[v]);
}
}
return 0;
}