Reincarnation

正因为梦易碎，才格外美好。

P4768 [NOI2018] 归程

发表于 更新于 分类于
本文字数： 5.4k 阅读时长 ≈ 5 分钟

「末世追忆」：”当梦想指路至无知的远方，醒来时分的少年，是否应该考虑随着漫雨，踏上归途。”

损失一个亿的调题技巧。（指错失了 的机会， 爷久久不能释怀）

洛谷指路和 官方的双倍经验。

首先， 都是 级别的，说明不能限制在 上，得考虑一大堆预处理。然后把图建出来之后会发现，因为车子只能使用一次，那么我们能够零体力到达的点一定是一个包含了起点，且海拔皆在水位线之上的一个连通块，而对于其他部分，最短路径不变，可以预处理：用 预处理可以达到 ，注意：这里并不能使用 ，会被卡掉。（出题人出言“ 已经死了”）

我们所求的答案就是该连通块 里的 。那有没有方法可以快速找到所在连通块，且与询问无关呢？考虑一种贪心思路，即按照海拔高度依次处理使得对于 则是之前所有里的答案。

然后我们还要保证连通，则肯定不考虑 查询，考虑 。如果是数据结构的话，可以考虑堆，满足顺序的性质，但是并不太好搞连通性，于是考虑从堆开始扩展，联想到 重构树，然后理所当然出来一个性质，海拔从子结点到父结点依次变小，然后用 表示以 为根的子树内的最小答案，一个简单的树型 直接 搞掉。

然后考虑如何从询问扩展到已处理部分——能够到达的连通块肯定满足 ，而重构树内海拔由小到大，我们就需要找到一个深度最小的点，满足 ，然后 就是我们所求的答案。

调了老半天的原因有几个，拿来避雷：

  • 在进行 预处理的时候，点数为 ，而在重构树之后，点数会变成 ，所以 for 循环应该套的是 Idx 而不是 N 。
  • 空间十分玄学（也不是很玄学），同样因为是重构树，导致很多东西都需要开到两倍。
  • 多组数据，记得清空；以及如果最短路和重构树共用一个链式前向星的话，也要记得清空。

因为打的时候比较紊乱，所以写的也就比较紊乱，所需要的变量都是定义在函数之前的，比较分散，也就导致 Dist[MAXN] 没有二倍。

AC Code 
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
// Problem: P4768 [NOI2018] 归程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4768
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
    x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
    x=x<y?x:y;
}
const int MAXN=2e5+10,MAXM=4e5+10;
int Test,N,M,Q,K,S,Val[MAXN<<1];
struct G
{
	int next,to,val;
}Edge[MAXM<<1];
struct Edges
{
	int u,v,h;
}Ed[MAXM];
int Head[MAXN<<1],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
inline void init()
{
	memset(Head,0,sizeof(Head)),Total=0;
	read(N,M);
	for(int i=1,u,v,l,h;i<=M;++i)
	{
		read(u,v,l,h);addEdge(u,v,l);
		Ed[i]=(Edges){u,v,h};
	}
	read(Q,K,S);
}
struct Que
{
	int x,d;
	Que(int x=0,int d=0):x(x),d(d){}
	bool operator<(const Que &x) const
	{
		return x.d<d;
	}
};
int Dist[MAXN];
bool Vis[MAXN];
inline void Dijkstra(int st)
{
	std::priority_queue<Que>Q;
	Q.push(Que(st,0));
	memset(Dist,0x3f,sizeof(Dist)),Dist[st]=0;
	memset(Vis,0,sizeof(Vis));
	while(!Q.empty())
	{
		int u=Q.top().x;Q.pop();
		if(Vis[u]) continue;
		Vis[u]=1;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(Dist[v]>Dist[u]+Edge[e].val)
			{
				Dist[v]=Dist[u]+Edge[e].val;
				if(!Vis[v]) Q.push(Que(v,Dist[v]));
			}
		}
	}
}
int Idx;
struct Dsu
{
    int Rt[MAXN<<1];
    inline void init(int n)
    {
        for(int i=1;i<=2*n;++i) Rt[i]=i;
    }
    inline int getRt(int x)
    {
        return Rt[x]==x?x:Rt[x]=getRt(Rt[x]);
    }
    inline int merge(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        Rt[p]=Rt[q]=++Idx;
        return Idx;
    }
    inline bool connect(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        return p==q;
    }
}Dsu;
inline bool cmp(Edges a,Edges b)
{
	return a.h>b.h;
}
inline void Kruskal()
{
	memset(Head,0,sizeof(Head)),Total=0;
	Idx=N;
	std::sort(Ed+1,Ed+M+1,cmp);
	Dsu.init(N);
	for(int i=1;i<=M;++i)
	{
		auto e=Ed[i];
		int p1=Dsu.getRt(e.u),p2=Dsu.getRt(e.v);
		if(p1==p2) continue;
		int lca=Dsu.merge(p1,p2);Val[lca]=e.h;
		addEdge(lca,p1,0),addEdge(lca,p2,0);
	}
}
int Dp[MAXN<<1],Mul[MAXN<<1][25];
void dfsTree(int x,int last)
{
	Dp[x]=Dist[x];
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Mul[v][0]=x;
		checkMin(Dp[x],Dp[v]);
	}
}
inline void Multi()
{
	for(int i=1;i<25;++i)
		for(int x=1;x<=Idx;++x)
			Mul[x][i]=Mul[Mul[x][i-1]][i-1];
}
inline int getLc(int x,int val)
{
	for(int i=24;i>=0;--i) if(Val[Mul[x][i]]>val) x=Mul[x][i];
	return x;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(Test);
    while(Test--)
    {
    	init();
    	Dijkstra(1),Kruskal();
    	dfsTree(Idx,0),Multi();
    	int lastans=0;
		for(int st,s;Q--;)
    	{
    		read(st,s);
			st=(st+K*lastans-1)%N+1,s=(s+K*lastans)%(S+1);
			write(lastans=Dp[getLc(st,s)],'\n');
    	}	
    }
    return 0;
}
/*

*/
相关文章