星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P4768 【[NOI2018]归程】

posted on 2018-07-19 09:10:02 | under 题解 |

写一下这位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

#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;
    }
}