提交记录 4567


用户 题目 状态 得分 用时 内存 语言 代码长度
langsike noi18a. 【NOI2018】归程 Accepted 100 1.528 s 92988 KB C++ 3.82 KB
提交时间 评测时间
2018-07-25 15:23:57 2020-07-31 23:08:05
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e14;
const int N=5e5;
const int M=1e6;
int t,tot,n,m;
int head[N+10];
struct data {
    int next,num;
    LL w;
}edge[M+10];
void Add(int u,int v,LL w) {
    edge[++tot].next=head[u];
    edge[tot].num=v;
    edge[tot].w=w;
    head[u]=tot;
}
struct node {
    LL dis;
    int loc;
    bool operator < (const node &p) const {
        return dis>p.dis;
    }
};
struct edges {
    int u,v;
    LL l,ax;
}e[M+10];
bool cmp(edges p,edges q) {
    return p.ax>q.ax;
}
priority_queue <node> q;
LL dis[N+10];
void Dijkstra() {
    for (int i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    node now;
    now.dis=0;
    now.loc=1;
    q.push(now);
    while (!q.empty()) {
        node now=q.top();
        q.pop();
        while (!q.empty()&&now.dis!=dis[now.loc]) {
            now=q.top();
            q.pop();
        }
        if (now.dis!=dis[now.loc]) break;
        for (int i=head[now.loc];i!=-1;i=edge[i].next) {
            int kx=edge[i].num;
            if (now.dis+edge[i].w<dis[kx]) {
                dis[kx]=now.dis+edge[i].w;
                node dx;
                dx.dis=dis[kx];
                dx.loc=kx;
                q.push(dx);
            }
        }
    }
}
vector <pair<int,int> > fa[N+10];
vector <pair<int,int> > min0[N+10];
vector <pair<int,int> > sz[N+10];
int GETF(int x) {
    if (fa[x][fa[x].size()-1].first==x) return x;
    return GETF(fa[x][fa[x].size()-1].first);
}
void prework() {
    for (int i=1;i<=n;i++) {
        fa[i].clear();
        min0[i].clear();
        sz[i].clear();
        fa[i].push_back(make_pair(i,0));
        min0[i].push_back(make_pair(dis[i],0));
        sz[i].push_back(make_pair(1,0));
    }
    sort(e+1,e+m+1,cmp);
    for (int i=1;i<=m;i++) {
        int u=e[i].u,v=e[i].v;
        int fu=GETF(u),fv=GETF(v);
        if (fu==fv) continue;
        if (sz[fu][sz[fu].size()-1].first>sz[fv][sz[fv].size()-1].first)
            swap(fu,fv);
        fa[fu].push_back(make_pair(fv,i));
        int minx=min0[fu][min0[fu].size()-1].first;
        minx=min(minx,min0[fv][min0[fv].size()-1].first);
        min0[fv].push_back(make_pair(minx,i));
        int nowsz=sz[fu][sz[fu].size()-1].first+sz[fv][sz[fv].size()-1].first;
        sz[fv].push_back(make_pair(nowsz,i));
    }
}
int getff(int x,int lim) {
    int l=0,r=fa[x].size()-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        if (fa[x][mid].second<=lim) l=mid;
        else r=mid-1;
    }
    return fa[x][l].first;
}
int getmin0(int x,int lim) {
    int l=0,r=min0[x].size()-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        if (min0[x][mid].second<=lim) l=mid;
        else r=mid-1;
    }
    return min0[x][l].first;
}
int getf(int x,int lim) {
    int ff=getff(x,lim);
    if (x==ff) return x;
    return getf(ff,lim);
}
int Calc(int px,int lim) {
    int fu=getf(px,lim);
    return getmin0(fu,lim);
}
void work() {
    int q,k,s;
    scanf("%d%d%d",&q,&k,&s);
    LL lst=0;
    while (q--) {
        LL v0,p0;
        scanf("%lld%lld",&v0,&p0);
        LL v=(v0+k*lst+n-1)%n+1;
        LL p=(p0+k*lst)%(s+1);
        int l=0,r=m;
        while (l<r) {
            int mid=(l+r+1)/2;
            if (e[mid].ax>p) l=mid;
            else r=mid-1;
        }
        int ans=Calc(v,l);
        printf("%d\n",ans);
        lst=ans;
    }
}
int main() {
    //freopen("return.in","r",stdin);
    //freopen("return.out","w",stdout);
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) head[i]=-1;
        tot=0;
        for (int i=1;i<=m;i++) {
            scanf("%d%d%lld%lld",&e[i].u,&e[i].v,&e[i].l,&e[i].ax);
            Add(e[i].u,e[i].v,e[i].l);
            Add(e[i].v,e[i].u,e[i].l);
        }
        Dijkstra();
        prework();
        work();
    }
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #16.039 ms34 MB + 372 KBAcceptedScore: 5

Testcase #26.053 ms34 MB + 384 KBAcceptedScore: 5

Testcase #36.174 ms34 MB + 396 KBAcceptedScore: 5

Testcase #46.48 ms34 MB + 412 KBAcceptedScore: 5

Testcase #510.523 ms34 MB + 876 KBAcceptedScore: 5

Testcase #6896.223 ms88 MB + 124 KBAcceptedScore: 5

Testcase #79.916 ms34 MB + 756 KBAcceptedScore: 5

Testcase #810.024 ms34 MB + 760 KBAcceptedScore: 5

Testcase #910.099 ms34 MB + 760 KBAcceptedScore: 5

Testcase #10637.912 ms77 MB + 732 KBAcceptedScore: 5

Testcase #11640.797 ms77 MB + 736 KBAcceptedScore: 5

Testcase #12903.912 ms87 MB + 364 KBAcceptedScore: 5

Testcase #13903.468 ms87 MB + 360 KBAcceptedScore: 5

Testcase #14903.835 ms87 MB + 356 KBAcceptedScore: 5

Testcase #1511.631 ms34 MB + 884 KBAcceptedScore: 5

Testcase #1611.512 ms34 MB + 884 KBAcceptedScore: 5

Testcase #17903.66 ms87 MB + 364 KBAcceptedScore: 5

Testcase #18902.691 ms87 MB + 360 KBAcceptedScore: 5

Testcase #191.528 s90 MB + 824 KBAcceptedScore: 5

Testcase #201.528 s90 MB + 828 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 21:51:05 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用