```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<sstream>
#include<iomanip>
#define pb push_back
#define mp make_pair
#define qr read()
#define LL long long
#define ff first
#define ss second
#define in inline
#define reg register
#define pa pair<int,int>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,a,b) for(int i = (a); i >= (b); i--)
using namespace std;
const int MAXN=0x3f3f3f3f;
const int MAXL=0x7ffff;
inline int read()
{
int x=0,k=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*k;
}
inline void write(int re)
{ /*
if (re<0)
{
putchar('-');
re=-re;
}
*/
if (re>9) write(re/10);
putchar(re%10+'0');
}
#define N 800000
int to[N + 10],nxt[N + 10],c[N / 2 + 10],hi[N + 10],len[N + 10],lfa;
struct app{
int u,v,l,h;
}e[N / 2 + 10];
int m,n;
int fa[N * 18],dep[N * 18],rt[N],ls[N * 18],rs[N * 18];
int Ls[N * 18],Rs[N * 18],Rt[N];
int Cnt;
int dis[N],vis[N];
int cnt;
LL lans;
int dist[N * 18];
inline void add(int u,int v,int l,int h)
{
cnt++;
to[cnt] = v;
len[cnt] = l;
hi[cnt] = h;
nxt[cnt] = c[u];
c[u] = cnt;
}
void reset()
{
cnt = 0;
Cnt = 0;
lans = 0;
memset(Rt,0,sizeof(Rt));
memset(Rs,0,sizeof(Rs));
memset(Ls,0,sizeof(Ls));
memset(fa,0,sizeof(fa));
memset(c,0,sizeof(c));
memset(ls,0,sizeof(ls));
memset(rs,0,sizeof(rs));
memset(dep,0,sizeof(dep));
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(dist,0x3f3f3f3f,sizeof(dist));
memset(rt,0,sizeof(rt));
memset(vis,0,sizeof(vis));
}
bool cmp(app aa,app bb)
{
return aa.h > bb.h;
}
void dij()
{
dis[1] = 0;
priority_queue<pa,vector<pa>,greater<pa> >q;
q.push(mp(0,1));
while(!q.empty())
{
pa t = q.top();
q.pop();
int now = t.ss;
int le = t.ff;
if(vis[now])continue;
vis[now] = 1;
for(int i = c[now];i ;i = nxt[i])
{
int v = to[i];
if(dis[v] > len[i] + le)
{
dis[v] = len[i] + le;
q.push(mp(dis[v],v));
}
}
}
}
int search(int x)
{
int l = 0,r = m,res = m + 1;
while(l <= r)
{
int mid = l + r >> 1;
if(e[mid].h > x)res = mid,l = mid + 1;
else r = mid - 1;
}
return res;
}
void Build(int &o,int l,int r)
{
o = ++Cnt;
if(l == r)
{
dist[o] = dis[l];
return;
}
int mid = l + r >> 1;
Build(Ls[o],l,mid);
Build(Rs[o],mid+1,r);
}
void build(int &o,int l,int r)
{
o = ++cnt;
if(l == r)
{
fa[o] = l;
return;
}
int mid = l + r >> 1;
build(ls[o],l,mid);
build(rs[o],mid+1,r);
}
void query(int o,int l,int r,int u)
{
if(l == r)
{
lfa = o;
return;
}
int mid = l + r >> 1;
if(u <= mid)query(ls[o],l,mid,u);
else query(rs[o],mid + 1,r,u);
}
void Query(int o,int l,int r,int u)
{
if(l == r)
{
lans = dist[o];
return;
}
int mid = l + r >> 1;
if(u <= mid)Query(Ls[o],l,mid,u);
else Query(Rs[o],mid + 1,r,u);
}
int find(int now,int x)
{
query(rt[now],1,n,x);
int d = lfa;
if(fa[d] == x)return d;
return find(now,fa[d]);
}
void add(int o,int l,int r,int u,int d)
{
if(l == r)
{
dep[o]++;
return;
}
int mid = l +r >> 1;
if(u <= mid)add(ls[o],l,mid,u);
else add(rs[o],mid + 1,r,u);
}
void update(int &o,int lst,int l,int r,int u,int t)
{
o = ++cnt;
dep[o] = dep[lst];
if(l == r)
{
fa[o] = t;
return;
}
ls[o] = ls[lst];
rs[o] = rs[lst];
int mid = l + r >> 1;
if(u <= mid)update(ls[o],ls[lst],l,mid,u,t);
else update(rs[o],rs[lst],mid+1,r,u,t);
}
void Update(int &o,int lst,int l,int r,int u,int t)
{
o = ++Cnt;
dist[o] = dist[lst];
if(l == r)
{
dist[o] = t;
return;
}
Ls[o] = Ls[lst];
Rs[o] = Rs[lst];
int mid = l + r >> 1;
if(u <= mid)Update(Ls[o],Ls[lst],l,mid,u,t);
else Update(Rs[o],Rs[lst],mid+1,r,u,t);
}
void merge(int now,int u,int v)
{
int fu = find(now,u);
int fv = find(now,v);
if(fa[fu] == fa[fv])return;
if(dep[fu] > dep[fv])swap(fu,fv);
LL d = 1000000000;
Query(Rt[now],1,n,fa[fu]);
d = min(d,lans);
Query(Rt[now],1,n,fa[fv]);
d = min (d,lans);
update(rt[now],rt[now - 1],1,n,fa[fu],fa[fv]);
if(dep[fu] == dep[fv])add(rt[now],1,n,fa[fv]);
Update(Rt[now],Rt[now - 1],1,n,fa[fv],d);
}
int T;
int main()
{
T = qr;
while(T--)
{
reset();
n = qr,m = qr;
rep(i,1,m)
{
e[i].u = qr,e[i].v = qr,e[i].l = qr,e[i].h = qr;
add(e[i].u,e[i].v,e[i].l,e[i].h);
add(e[i].v,e[i].u,e[i].l,e[i].h);
}
cnt = 0;
dij();
build(rt[0],1,n);
Build(Rt[0],1,n);
sort(e + 1,e + 1 + m,cmp);
rep(i,1,m)
{
rt[i] = rt[i - 1];
Rt[i] = Rt[i - 1];
merge(i,e[i].u,e[i].v);
}
int Q = qr,K = qr,S =qr;
lans = 0;
while(Q--)
{
int v0 = (qr + K * lans - 1) % n + 1;
int p0 = (qr + K * lans) % (S + 1);
int pos = search(p0);
if(pos == m + 1)
{
lans = dis[v0];
cout << dis[v0] << endl;
continue;
}
Query(Rt[pos],1,n,fa[find(pos,v0)]);
printf("%lld\n",lans);
}
}
}
```
代码
by www2003 @ 2019-08-20 10:26:40
@[www2003](/space/show?uid=87651) ~~开大数组~~
by QwQ蒟蒻wjr @ 2019-08-20 10:32:33
@[蒟蒻wjr](/space/show?uid=133322) 再大会MLE
by www2003 @ 2019-08-20 10:33:54
@[蒟蒻wjr](/space/show?uid=133322) 我觉得我数组开的也不小但是一到N<=200000就RE了
by www2003 @ 2019-08-20 10:35:16
等等，你的主席树可能要N*25
by QwQ蒟蒻wjr @ 2019-08-20 10:54:38
@[www2003](/space/show?uid=87651)
by QwQ蒟蒻wjr @ 2019-08-20 10:55:42
@[蒟蒻wjr](/space/show?uid=133322) 好吧谢谢，那得重新写一些了，25必然MLE
by www2003 @ 2019-08-20 11:05:13
@[蒟蒻wjr](/space/show?uid=133322) ~~主席树通常不是要开到32倍级别的吗。。。~~
by HRLYB @ 2019-08-27 11:13:40
@[HRLYB](/space/show?uid=126621) 具体情况具体做
by QwQ蒟蒻wjr @ 2019-08-27 12:36:47