[NOI2018]归程

Description

BZOJ5415(权限题)
Luogu 4768

Solution

按照给出的测试点来思考部分分。

Part 1

这部分海拔只有1种，只需求一个最短路，然后判断水位是否大于这个海拔，求解即可。

Part 2

这部分是一条链或一棵树，由于深度越小答案越优，所以就在海拔不超过h的边上尽可能的向上走（用并查集模拟这个过程，排序询问后离线处理）。

Part 3

这部分是离线部分，直接看Part 4吧

Part 4

这部分强制在线，注意到并查集重构树中满足高度度递减，那么可以建立重构树，并计算出每个节点子树中的最短路最小值。询问时倍增的向上寻找高度大于水位线的深度最小的节点，统计答案即可。

Code

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

typedef long long ll;
const int N = 4e5 + 10;
const int M = 8e5 + 10;

int n, m, cnt, cur;
struct edge {
    int u, v, l, a;
    edge* nxt;
    edge(int u = 0, int v = 0, int l = 0, int a = 0, edge* nxt = nullptr) :
        u(u), v(v), l(l), a(a), nxt(nxt) {}
    bool operator < (const edge& x) const {
        return a > x.a;
    }
} e[M], tr[M];
edge *hd[N], *td[N];
struct node {
    int p, d;
    node(int x=0, int y=0) : p(x), d(y) {}
    bool operator < (const node &x) const {
        return d > x.d;
    }
};
ll dis[N], vis[N], tw[N];
int tot;
int fa[N], pa[N][20], tt[N];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

ll calc(int o, ll h) {
    for (int i = 19; i >= 0; --i) if (pa[o][i] && tt[pa[o][i]] > h) o = pa[o][i];
    return tw[o];
}

inline void init() {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(pa, 0, sizeof pa);
    memset(tt, 0, sizeof tt);
    for (int i = 1; i <= cnt; ++i) e[i] = edge(0, 0, 0, 0, nullptr);
    for (int i = 1; i <= cur; ++i) tr[i] = edge(0, 0, 0, 0, nullptr);
    for (int i = 1; i <= tot; ++i) hd[i] = td[i] = nullptr;
    cnt  = cur = tot = 0;
    for (int i = 1; i <= n<<1; ++i) fa[i] = i, tw[i] = 0x3f3f3f3f;
}

inline void adde(int u, int v, int l, int a) {
    cnt++;
    e[cnt] = edge(u, v, l, a, hd[u]);
    hd[u] = &e[cnt];
}

inline void addtr(int u, int v) {
    cur++;
    tr[cur] = edge(u, v, 0, 0, td[u]);
    td[u] = &tr[cur];
}

std::priority_queue<node> q;

inline void dijstra() {
    dis[1] = 0; q.push(node(1, 0));
    node tmp;
    while (!q.empty()) {
        tmp = q.top(); q.pop();
        if (vis[tmp.p]) continue;
        vis[tmp.p] = 1;
        for (edge *x = hd[tmp.p]; x != nullptr; x = x->nxt) if (!vis[x->v]) {
            if (dis[x->v] > tmp.d + x->l) {
                dis[x->v] = tmp.d + x->l;
                q.push(node(x->v, dis[x->v]));
            }
        }
    }
}

ll dfs(int x, int f) {
    pa[x][0] = f;
    for (int i = 1; i < 20; ++i) pa[x][i] = pa[pa[x][i-1]][i-1];
    for (edge *nw = td[x]; nw != nullptr; nw = nw->nxt) {
        tw[x] = std::min(tw[x], dfs(nw->v, x));
    }
    if (x <= n) tw[x] = std::min(tw[x], dis[x]);
    return tw[x];
}

inline void kruskal() {
    std::sort(e+1, e+cnt+1);
    tot = n;
    for (int i = 1; i <= cnt; i++) {
    	if (tot == (n<<1) - 1) break;
    	int &x = e[i].u, &y = e[i].v;
        int fx = find(x), fy = find(y);
    	if (fx != fy) {
        	tot++;
       	 	fa[fx] = tot;
      	  	fa[fy] = tot;
        	addtr(tot, fx);
        	addtr(tot, fy);
        	tt[tot] = e[i].a;
    	} 
    } 
    dfs(tot, 0);
}

ll read() {
	char c;
	while (!isdigit(c=getchar()));
	ll ans = c^48;
	while (isdigit(c=getchar())) ans = (ans<<3)+(ans<<1)+(c^48);
	return ans;
}

int main() {
	int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        init();
        for (int i = 1, u, v, l, a; i <= m; ++i) {
            u = read(), v = read(), l = read(), a = read();
            adde(u, v, l, a);
            adde(v, u, l, a);
        }
        
        dijstra();
        ll s; int q, k;
        scanf("%d%d%lld", &q, &k, &s);
        kruskal();
        ll ans = 0, v, p;
        for (int i = 1; i <= q; ++i) {
            v = read(), p = read();
            v = (v + k*ans - 1) % n + 1;
            p = (p + k*ans) % (s+1);
            ans = calc(v, p);
            printf("%lld
", ans);
        }
    }
}