AC on 1~5

WA on 6~20

详情链接

#include <bits/stdc++.h>
using namespace std;
namespace Radon{
    void Main();
}
int main(){
    Radon::Main();
    return 0;
}

namespace Radon{
    #define N 200100
    #define int long long
    #define PLL pair<int,int>
    int CNT=0;
    inline int read(){
        int a=0,f=1;
        char c=getchar();
        while(c<'0' || c>'9'){
            if(c=='-'){
                f=-1;
            }
            c=getchar();
        }
        c=getchar();
        while(c>='0' && c<='9'){
            a=(a<<1)+(a<<3)+c-'0';
            c=getchar();
        }
        return a*f;
    }
    struct node{
        int v,w;
    };
    struct edge{
        int u,v,w;
    };
    vector<edge>e;
    bool cmp(edge a,edge b){
        return a.w>b.w;
    }



    int f[N<<3];
    int find(int x){
        if(x==f[x]){
            return x;
        }
        f[x]=find(f[x]);
        return f[x];
    }



    int n,m,s,minx,lastans;
    int Q,K,S,dis[N];
    struct point{
        int minx,val;
    }k[N<<3];
    int fa[N<<3],ls[N<<3],rs[N<<3],cnt=0;
    int SS[N<<3][100],dep[N<<3];
    int vis[N<<3];
    vector<node>g[N<<3];


    void dji(){
        priority_queue<PLL,vector<PLL>,greater<PLL> >q;
        dis[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty()){
            int u=q.top().second;
            q.pop();
            if(vis[u]){
                continue;
            }
            vis[u]=1;
            for(int x=0;x<g[u].size();x++){
                node to=g[u][x];
                if(dis[to.v]>dis[u]+to.w){
                    dis[to.v]=dis[u]+to.w;
                    q.push(make_pair(dis[to.v],to.v));
                }
            }
        }
    }

//242641

    void dfs(int u,int father){
        // cout << "QwQ" << u << " " << father << endl;
        dep[u]=dep[father]+1;
        // CNT++;
        // cout << u << ':' << father << endl;
        SS[u][0]=father;
        for(int x=1;x<=19;x++){
            SS[u][x]=SS[SS[u][x-1]][x-1];
        }
        if(ls[u]!=0){
            dfs(ls[u],u);
        }
        if(rs[u]!=0){
            dfs(rs[u],u);
        }
    }


    void kruskal(){
        for(int x=1;x<=n;x++){
            k[++cnt].minx=dis[x];
            k[cnt].val=0;
        }
        // sort(e+1,e+1+m,cmp);
        for(int x=0;x<m;x++){
            int u=e[x].u;
            int v=e[x].v;
            int w=e[x].w;
            int fu=find(u),fv=find(v);
            // cout << "QAQ" << u << " " << v << " " << fu << " " << fv << endl;
            if(fu==fv){
                continue;
            }
            fa[fu]=++cnt;
            fa[fv]=cnt;
            f[fu]=f[fv]=f[cnt]=cnt;
            k[cnt].minx=min(k[fu].minx,k[fv].minx);
            k[cnt].val=w;
            ls[cnt]=fu;rs[cnt]=fv;
        }
        // for(int x=1;x<=cnt;x++){
        //     cout << x << ':' << k[x].minx << endl;
        // }
        dfs(cnt,0);
    }


    int query(int X,int Y){
        // cout << "QWQ" << X << " ";
        for(int x=19;x>=0;x--){
            if(dep[X]-(1<<x)>0 && k[SS[X][x]].val>Y){
                X=SS[X][x];
            }
        }
        // cout << X << endl;
        return k[X].minx;
    }


    // int t[N<<5];
    // void build(int x,int l,int r,int num,int val){
    //     if(l==r){
    //         t[x]=val;
    //         return;
    //     }
    //     int mid=(l+r)>>1;
    //     if(mid>=num){
    //         build(x<<1,l,mid,num,val);
    //     }
    //     if(mid<num){
    //         build(x<<1|1,mid+1,r,num,val);
    //     }
    //     t[x]=min(t[x<<1],t[x<<1|1]);
    // }
    // int query(int x,int l,int r,int L,int R){
    //     if(l>=L && r<=R){
    //         return t[x];
    //     }
    //     int mid=(l+r)>>1;
    //     int ans=INF;
    //     if(mid>=L){
    //         ans=min(ans,query(x<<1,l,mid,L,R));
    //     }
    //     if(mid<R){
    //         ans=min(ans,query(x<<1|1,mid+1,r,L,R));
    //     }
    //     return ans;
    // }


    void init(){
        // memset(t,0x7f,sizeof(t));
        memset(ls,0,sizeof(ls));
        memset(fa,0,sizeof(fa));
        for(int x=1;x<=cnt;x++){
            k[x].minx=0;
            k[x].val=0;
        }
        cnt=0;
        memset(vis,0,sizeof(vis));
        memset(rs,0,sizeof(rs));
        memset(dis,0x3f,sizeof(dis));
        for(int x=1;x<=n;x++){
            f[x]=x;
        }
        for(int x=0;x<=N-5;x++){
            g[x].clear();
        }
        lastans=0;
    }


    void Main(){
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
        int T,lastans=0;
        // freopen("P4768_5.in","r",stdin);
        // freopen("P4768.out","w",stdout);
        cin >> T;
        while(T--){
            // n=read();
            // m=read();
            cin >> n >> m;
            init();
            for(int x=1;x<=m;x++){
                int u,v,w,l;
                // u=read();v=read();w=read();l=read();
                cin >> u >> v >> w >> l;
                g[u].push_back({v,w});
                g[v].push_back({u,w});
                e.push_back({u,v,l});
            }
            sort(e.begin(),e.end(),cmp);
            // Q=read();K=read();S=read();
            cin >> Q >> K >> S;
            dji();
            kruskal();
            for(int i=1;i<=Q;i++){
                int v,p;
                // v=read();
                // p=read();
                cin >> v >> p;
                s=(v+K*lastans-1)%n+1;
                minx=(p+K*lastans)%(S+1);
                cout << (lastans=query(s,minx)) << endl;
            }
        }
    }
}```