题解 P4768 【[NOI2018]归程】

写一下这位dalao@栓犬 告诉我的做法。$Orz$ $Dijkstra$之后~~（出题人：$Spfa$死了）~~，有一个很显然的离线想法是，询问与边都按从大到小排序，然后每次询问倒序进去的时候按比海拔高的约束加入能开车的边，这个东西可以用并查集维护。每次维护这个点子树的最小距离，直接输出就好了。复杂度$O(n\log m+m\log n+q\log n)$。~~然后就有许多同学直接用可持久化并查集直接$O(n\log m+m\log n+q\log ^2n)$暴力艹过去了~~ 但实际上这题是可以写到$1$个$\log$的，除了$Kruskal$重构树之外，还可以用$vector$+二分的做法。 我们可以发现，边排序后，答案随着高度变低、并查集合并而逐渐减少，即对于每个点，答案都具有单调递减性。 我们可以开一个$vector$记录每个点在以高度为版本（高度越高，版本越老）的答案，于是并查集合并时直接把小的答案加入父亲的$vector$里。在询问时，找到最近的版本比它老的答案最小的版本，也就是最靠近它且高度比它大的版本。 注意每个点先加入一个版本为$inf$，答案为$dis_i$的答案。 用启发式合并保证复杂度，总时间复杂度为$O(n\log m+m\log n+q\log n)$。 ~~还有没有人和我一样考场上没清空$lastans$拿了$65/70pts$的选手啊qwq~~ ```cpp #include<cstdio> #include<cstring> #include<queue> #include<ext/pb_ds/assoc_container.hpp> #define neko 1000010 #define meko 1000010 #define qeko 1000010 #define fi first #define se second #define chkmin(a,b) ((a)<(b)?(a):(b)) #define chkmax(a,b) ((a)>(b)?(a):(b)) #define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i))) using namespace std; typedef long long ll; typedef pair<ll,int> pi; struct qwq {ll ver,ans;}; vector<qwq>vec[neko]; struct node {int u,v,h,nex;ll w;}e[meko<<1],E[meko]; int t,Et,tp,n,m,Q,K,maxA; typedef int arr[neko]; arr head,fa,verfa,book,dep; ll mindis[neko],dis[neko],ans[neko],inf=2e9+1e8,lastans; template<typename T> void read(T &x) { char c=getchar();x=0; while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<1)+(x<<3)+(c^'0'),c=getchar(); } namespace Path { void add(int x,int y,ll z,int o) { e[++t].u=E[++Et].u=x; e[t].v=E[Et].v=y; e[t].w=E[Et].w=z; e[t].h=E[Et].h=o; e[t].nex=head[x]; head[x]=t; e[++t].u=y; e[t].v=x; e[t].w=z; e[t].h=o; e[t].nex=head[y]; head[y]=t; } void dijkstra() { priority_queue<pi,vector<pi>,greater<pi> >q; memset(dis,0x3f,sizeof(dis)); dis[1]=0,q.push(pi(0,1)); int u;pi x; while(!q.empty()) { x=q.top(),q.pop(); u=x.se; if(!book[u]) { book[u]=1; for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v) { if(dis[v]>=x.fi+e[i].w) { dis[v]=x.fi+e[i].w; q.push(pi(dis[v],v)); } } } } } } namespace Uset { int find(int x) { while(fa[x])x=fa[x]; return x; } void insert(int x,ll nowans,ll ver) { int len=vec[x].size()-1; if(nowans<vec[x][len].ans)vec[x].push_back((qwq){ver,nowans}); //printf("xx %lld %lld\n",ver,nowans); } void merge(int u,int v,ll w) { int x=find(u),y=find(v); if(x^y) { if(dep[x]>dep[y])std::swap(x,y); fa[x]=y,verfa[x]=w; dep[y]=chkmax(dep[x]+1,dep[y]); insert(y,vec[x][vec[x].size()-1].ans,w); } } ll solve(int x,int ver) { while(fa[x]&&verfa[x]>ver)x=fa[x]; ll now=2e9+1e8; int l=0,r=vec[x].size()-1; while(l<=r) { int mid=(l+r)>>1; if(vec[x][mid].ver>ver)now=chkmin(now,vec[x][mid].ans),l=mid+1; else r=mid-1; }return lastans=now; } void init() {memset(dep,0,sizeof(dep)),memset(fa,0,sizeof(fa));} } void Init() { memset(book,0,sizeof(book)); memset(head,0,sizeof(head)); t=Et=lastans=0; } bool cmp2(node a,node b) {return a.h>b.h;} int main() { using namespace Path; using namespace Uset; int x,y,o,cas;ll z; read(cas); while(cas--) { Init(); read(n),read(m); f(i,1,m) { read(x),read(y),read(z),read(o); add(x,y,z,o); }dijkstra(),init(); f(i,1,n)vec[i].clear(),vec[i].push_back((qwq){inf,dis[i]}); sort(E+1,E+Et+1,cmp2); f(i,1,m)merge(E[i].u,E[i].v,E[i].h); read(Q),read(K),read(maxA); f(i,1,Q) { read(x),read(y); x=(x+K*lastans-1)%n+1,y=(y+K*lastans)%(maxA+1); printf("%lld\n",solve(x,y)); } //cerr<<clock()<<endl; } } ```