代码

// NOI2018 归程 (Journey)
//   K==0 (offline): sort queries by water level + DSU merge with component min-dist
//   K==1 (online) : Kruskal reconstruction tree + packed binary-lifting table
// Reads stdin straight from the DuckInfo input buffer (already resident in memory).
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <sys/auxv.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;

struct DI { u64 abi; const char *in; u64 insz; char *out; u64 outlim; u64 outsz; char *err;
            u64 errlim; u64 errsz; const char *IB; u64 IBlim; char *OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));

static unsigned char *IP;
static inline ll rd(unsigned char *&p) {
    unsigned char c = *p;
    while (c < '0') c = *++p;
    ll x = 0;
    do { x = x * 10 + (c - '0'); c = *++p; } while (c >= '0');
    return x;
}

#define MAXN 200005
#define MAXM 400005
#define MAXQ 400005
#define LOG 19

static int n, m, tot;
static u32 eu[MAXM], ev[MAXM], el[MAXM], ea[MAXM];
static u32 eord[MAXM], tmp[MAXM], eo2[MAXM];
static u32 deg[MAXN + 2], cstart[MAXN + 2], fill_[MAXN + 2];
static u32 adj_to[2 * MAXM], adj_w[2 * MAXM];
static u32 dst[MAXN + 1];
static u32 dsu[2 * MAXN], tp[2 * MAXN];
static u32 tval[2 * MAXN], tlc[2 * MAXN], trc[2 * MAXN], tmin[2 * MAXN];
static u64 upT[2 * MAXN][LOG];
static u32 uplev[LOG][2 * MAXN];
static u32 trbuf[LOG][1024];
static u64 heap[2 * MAXM + 8];
static int hn;
#define RH_NIL 0xFFFFFFFFu
static u32 rh_head[32], rh_next[2 * MAXM + 8], rh_key[2 * MAXM + 8], rh_node[2 * MAXM + 8];
static u32 rh_cnt, rh_last, rh_sz;
static u32 lastans;
static u32 qv[MAXQ], qp[MAXQ], qord[MAXQ], qtmp[MAXQ], qans[MAXQ];
static u32 dmn[MAXN + 1];
static u32 cnt16[65536];

static inline void rh_clear() {
    for (int i = 0; i < 32; i++) rh_head[i] = RH_NIL;
    rh_cnt = 0; rh_last = 0; rh_sz = 0;
}
static inline void rh_push(u32 key, u32 node) {
    int i = key ? (31 - __builtin_clz(key ^ rh_last)) : 0;
    u32 e = rh_cnt++;
    rh_key[e] = key; rh_node[e] = node; rh_next[e] = rh_head[i]; rh_head[i] = e; rh_sz++;
}
static inline u32 rh_pop() {
    for (;;) {
        if (rh_head[0] != RH_NIL) {
            u32 e = rh_head[0]; rh_head[0] = rh_next[e]; rh_sz--;
            return rh_node[e];
        }
        int k = 1;
        while (rh_head[k] == RH_NIL) k++;
        u32 mn = 0xFFFFFFFFu;
        for (u32 e = rh_head[k]; e != RH_NIL; e = rh_next[e]) if (rh_key[e] < mn) mn = rh_key[e];
        rh_last = mn;
        u32 e = rh_head[k];
        rh_head[k] = RH_NIL;
        while (e != RH_NIL) {
            u32 nx = rh_next[e];
            int j = rh_key[e] ? (31 - __builtin_clz(rh_key[e] ^ rh_last)) : 0;
            rh_next[e] = rh_head[j]; rh_head[j] = e;
            e = nx;
        }
    }
}
static inline void hpush(u64 v) {
    int i = hn++;
    while (i) { int p = (i - 1) >> 1; if (heap[p] <= v) break; heap[i] = heap[p]; i = p; }
    heap[i] = v;
}
static inline u64 hpop() {
    u64 top = heap[0], v = heap[--hn];
    int i = 0;
    while (true) {
        int c = 2 * i + 1;
        if (c >= hn) break;
        if (c + 1 < hn && heap[c + 1] < heap[c]) c++;
        if (heap[c] >= v) break;
        heap[i] = heap[c]; i = c;
    }
    if (hn) heap[i] = v;
    return top;
}
static u32 find(u32 x) { while (dsu[x] != x) { dsu[x] = dsu[dsu[x]]; x = dsu[x]; } return x; }

int main() {
    DI *di = (DI *)getauxval(0x6b637564ULL);
    if (di && di->in && di->insz) { IP = (unsigned char *)di->in; }
    else {
        static unsigned char *lbuf = (unsigned char *)malloc(1u << 28);
        size_t r = fread(lbuf, 1, 1u << 28, stdin); (void)r; IP = lbuf;
    }

    ll T = rd(IP);
    static char *obuf = (char *)malloc(1 << 26);
    size_t olen = 0;

    while (T-- > 0) {
        lastans = 0;
        n = (int)rd(IP); m = (int)rd(IP);
        for (int i = 0; i < m; i++) {
            eu[i] = (u32)rd(IP); ev[i] = (u32)rd(IP); el[i] = (u32)rd(IP); ea[i] = (u32)rd(IP);
        }
        // ---- CSR adjacency + Dijkstra from node 1 ----
        memset(deg, 0, (n + 2) * sizeof(u32));
        for (int i = 0; i < m; i++) { deg[eu[i]]++; deg[ev[i]]++; }
        u32 s = 0;
        for (int i = 1; i <= n; i++) { cstart[i] = s; s += deg[i]; }
        cstart[n + 1] = s;
        memcpy(fill_, cstart, (n + 2) * sizeof(u32));
        for (int i = 0; i < m; i++) {
            u32 u = eu[i], v = ev[i], w = el[i];
            adj_to[fill_[u]] = v; adj_w[fill_[u]] = w; fill_[u]++;
            adj_to[fill_[v]] = u; adj_w[fill_[v]] = w; fill_[v]++;
        }
        for (int i = 1; i <= n; i++) dst[i] = 0xFFFFFFFFu;
        dst[1] = 0; rh_clear(); rh_push(0, 1);
        while (rh_sz) {
            u32 u = rh_pop();
            u32 d = dst[u];
            for (u32 e = cstart[u]; e < cstart[u + 1]; e++) {
                u32 v = adj_to[e];
                u32 nd = d + adj_w[e];
                if (nd < dst[v]) { dst[v] = nd; rh_push(nd, v); }
            }
        }
        // ---- edges sorted by altitude, descending (LSD radix, 2x16 bits) ----
        memset(cnt16, 0, sizeof(cnt16));
        for (int i = 0; i < m; i++) cnt16[ea[i] & 0xFFFF]++;
        {
            u32 acc = 0;
            for (int k = 0; k < 65536; k++) { u32 c = cnt16[k]; cnt16[k] = acc; acc += c; }
        }
        for (int i = 0; i < m; i++) tmp[cnt16[ea[i] & 0xFFFF]++] = i;
        memset(cnt16, 0, sizeof(cnt16));
        for (int i = 0; i < m; i++) cnt16[(ea[tmp[i]] >> 16) & 0xFFFF]++;
        {
            u32 acc = 0;
            for (int k = 0; k < 65536; k++) { u32 c = cnt16[k]; cnt16[k] = acc; acc += c; }
        }
        for (int i = 0; i < m; i++) eo2[cnt16[(ea[tmp[i]] >> 16) & 0xFFFF]++] = tmp[i];
        for (int i = 0; i < m; i++) eord[i] = eo2[m - 1 - i];

        ll Q = rd(IP), K = rd(IP), S = rd(IP);
        if (K == 0) {
            // ---------- offline: queries sorted by descending p ----------
            for (ll q = 0; q < Q; q++) { qv[q] = (u32)rd(IP); qp[q] = (u32)rd(IP); }
            memset(cnt16, 0, sizeof(cnt16));
            for (ll q = 0; q < Q; q++) cnt16[qp[q] & 0xFFFF]++;
            {
                u32 acc = 0;
                for (int k = 0; k < 65536; k++) { u32 c = cnt16[k]; cnt16[k] = acc; acc += c; }
            }
            for (ll q = 0; q < Q; q++) qtmp[cnt16[qp[q] & 0xFFFF]++] = (u32)q;
            memset(cnt16, 0, sizeof(cnt16));
            for (ll q = 0; q < Q; q++) cnt16[(qp[qtmp[q]] >> 16) & 0xFFFF]++;
            {
                u32 acc = 0;
                for (int k = 0; k < 65536; k++) { u32 c = cnt16[k]; cnt16[k] = acc; acc += c; }
            }
            for (ll q = 0; q < Q; q++) qord[cnt16[(qp[qtmp[q]] >> 16) & 0xFFFF]++] = qtmp[q];
            for (int i = 1; i <= n; i++) { dsu[i] = (u32)i; dmn[i] = dst[i]; }
            int ep = 0;
            for (ll qi = Q - 1; qi >= 0; qi--) {
                u32 qid = qord[qi], p = qp[qid];
                while (ep < m && ea[eord[ep]] > p) {
                    u32 a = find(eu[eord[ep]]), b = find(ev[eord[ep]]);
                    ep++;
                    if (a == b) continue;
                    if (dmn[a] <= dmn[b]) dsu[b] = a; else dsu[a] = b;
                }
                qans[qid] = dmn[find(qv[qid])];
            }
            for (ll q = 0; q < Q; q++) {
                u32 x = qans[q];
                char tb[12]; int tl = 0;
                if (!x) tb[tl++] = '0';
                while (x) { tb[tl++] = (char)('0' + x % 10); x /= 10; }
                while (tl) obuf[olen++] = tb[--tl];
                obuf[olen++] = '\n';
                if (olen > (1 << 26) - 32) { fwrite(obuf, 1, olen, stdout); olen = 0; }
            }
        } else {
            // ---------- online: Kruskal reconstruction tree ----------
            for (int i = 1; i <= n; i++) { dsu[i] = (u32)i; tp[i] = 0; tval[i] = 0xFFFFFFFFu; tmin[i] = dst[i]; }
            tot = n;
            for (int i = 0; i < m; i++) {
                u32 id = eord[i];
                u32 a = find(eu[id]), b = find(ev[id]);
                if (a == b) continue;
                int t = ++tot;
                tval[t] = ea[id];
                tlc[t] = a; trc[t] = b;
                tp[a] = (u32)t; tp[b] = (u32)t;
                dsu[a] = (u32)t; dsu[b] = (u32)t; dsu[t] = (u32)t;
                tp[t] = 0;
            }
            for (int t = n + 1; t <= tot; t++) {
                u32 x = tmin[tlc[t]], y = tmin[trc[t]];
                tmin[t] = x < y ? x : y;
            }
            tval[0] = 0; tmin[0] = 0xFFFFFFFFu;
            // level-major build (sequential, cache friendly), then blocked transpose
            for (int k = 0; k < LOG; k++) uplev[k][0] = 0;
            for (int i = 1; i <= tot; i++) uplev[0][i] = tp[i];
            for (int k = 1; k < LOG; k++) {
                u32 *cur = uplev[k], *prv = uplev[k - 1];
                for (int i = 1; i <= tot; i++) cur[i] = prv[prv[i]];
            }
            for (int i0 = 1; i0 <= tot; i0 += 1024) {
                int bn = tot - i0 + 1;
                if (bn > 1024) bn = 1024;
                for (int k = 0; k < LOG; k++) {
                    u32 *src = uplev[k] + i0;
                    u32 *dst = trbuf[k];
                    for (int j = 0; j < bn; j++) dst[j] = src[j];
                }
                for (int j = 0; j < bn; j++) {
                    u64 *row = upT[i0 + j];
                    for (int k = 0; k < LOG; k++) {
                        u32 a = trbuf[k][j];
                        row[k] = ((u64)tval[a] << 32) | (u64)a;
                    }
                }
            }
            for (ll q = 0; q < Q; q++) {
                ll v0 = rd(IP), p0 = rd(IP);
                u32 v = (u32)((v0 + (ll)lastans - 1) % n + 1);
                u32 p = (u32)((p0 + (ll)lastans) % (S + 1));
                u32 u = v;
                for (int k = LOG - 1; k >= 0; k--) {
                    u64 e = upT[u][k];
                    if ((u32)(e >> 32) > p) u = (u32)e;
                }
                u32 ans = tmin[u];
                lastans = ans;
                char tb[12]; int tl = 0;
                if (!ans) tb[tl++] = '0';
                while (ans) { tb[tl++] = (char)('0' + ans % 10); ans /= 10; }
                while (tl) obuf[olen++] = tb[--tl];
                obuf[olen++] = '\n';
                if (olen > (1 << 26) - 32) { fwrite(obuf, 1, olen, stdout); olen = 0; }
            }
        }
    }
    if (olen) fwrite(obuf, 1, olen, stdout);
    return 0;
}

评测结果