代码

// NOI2018 归程 (noi18a)
// Kruskal reconstruction tree + Dijkstra + binary lifting, direct memory IO.
#include <sys/auxv.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

typedef unsigned int u32;
typedef unsigned long long u64;

#define MAXN 200002
#define MAXM 400002
#define LOG 19

// ---- DuckInfo ----
struct DuckInfo {
  u64 abi_version;
  const char *stdin_ptr; u64 stdin_size;
  char *stdout_ptr; u64 stdout_limit; u64 stdout_size;
  char *stderr_ptr; u64 stderr_limit; u64 stderr_size;
  const char *IB_ptr; u64 IB_limit;
  char *OB_ptr; u64 OB_limit;
  u64 tsc_frequency;
} __attribute__((packed));

static const char *sp;
static const char *sendp;

static inline int rd() {
  const char *p = sp;
  while (*p < '0' || *p > '9') p++;
  int x = 0;
  while (*p >= '0' && *p <= '9') { x = x * 10 + (*p - '0'); p++; }
  sp = p;
  return x;
}

// ---- adjacency (forward star) ----
static int head[MAXN];
static int to[2 * MAXM];
static u32 wt[2 * MAXM];
static int nxt[2 * MAXM];

// ---- edges ----
static int eu[MAXM], ev[MAXM];
static u32 el[MAXM], ea[MAXM];

// ---- radix sort ----
static int order[MAXM], tmp[MAXM];

// ---- Dijkstra ----
static u32 dist[MAXN];
static u64 heap[2 * MAXM + 2];

// ---- DSU / reconstruction tree ----
static int dsu[MAXN], sz[MAXN], rep[MAXN];
static u32 val[2 * MAXN];
static u32 mn[2 * MAXN];
static int up[LOG][2 * MAXN];

static int find(int x) {
  int r = x;
  while (dsu[r] != r) r = dsu[r];
  while (dsu[x] != x) { int nx = dsu[x]; dsu[x] = r; x = nx; }
  return r;
}

static char *op;

static inline void put_u32(u32 x) {
  char *o = op;
  if (x == 0) { *o++ = '0'; *o++ = '\n'; op = o; return; }
  char buf[16];
  int n = 0;
  while (x) { buf[n++] = (char)('0' + (x % 10)); x /= 10; }
  while (n) *o++ = buf[--n];
  *o++ = '\n';
  op = o;
}

int main() {
  struct DuckInfo *di = (struct DuckInfo *)getauxval(0x6b637564);
  sp = di->stdin_ptr;
  sendp = sp + di->stdin_size;
  op = di->stdout_ptr;

  int T = rd();
  while (T--) {
    int n = rd(), m = rd();

    // read edges
    for (int i = 0; i < m; i++) {
      eu[i] = rd(); ev[i] = rd(); el[i] = (u32)rd(); ea[i] = (u32)rd();
    }
    int Q = rd(), K = rd();
    u32 S = (u32)rd();

    // build adjacency
    for (int i = 1; i <= n; i++) head[i] = 0;
    int ecnt = 0;
    for (int i = 0; i < m; i++) {
      int u = eu[i], v = ev[i];
      u32 l = el[i];
      to[++ecnt] = v; wt[ecnt] = l; nxt[ecnt] = head[u]; head[u] = ecnt;
      to[++ecnt] = u; wt[ecnt] = l; nxt[ecnt] = head[v]; head[v] = ecnt;
    }

    // Dijkstra from node 1
    for (int i = 1; i <= n; i++) dist[i] = 0xFFFFFFFFu;
    dist[1] = 0;
    int hsz = 1;
    heap[1] = 1ull; // dist 0 << 32 | node 1
    while (hsz) {
      u64 key = heap[1];
      int u = (int)(key & 0xFFFFFFFFu);
      u32 d = (u32)(key >> 32);
      if (d != dist[u]) { // stale
        u64 last = heap[hsz--];
        int i = 1;
        while (1) {
          int l = i << 1;
          if (l > hsz) break;
          int r = l + 1;
          int c = (r <= hsz && heap[r] < heap[l]) ? r : l;
          if (last <= heap[c]) break;
          heap[i] = heap[c]; i = c;
        }
        heap[i] = last;
        continue;
      }
      { // pop
        u64 last = heap[hsz--];
        int i = 1;
        while (1) {
          int l = i << 1;
          if (l > hsz) break;
          int r = l + 1;
          int c = (r <= hsz && heap[r] < heap[l]) ? r : l;
          if (last <= heap[c]) break;
          heap[i] = heap[c]; i = c;
        }
        heap[i] = last;
      }
      for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        u32 nd = d + wt[e];
        if (nd < dist[v]) {
          dist[v] = nd;
          u64 nk = ((u64)nd << 32) | (u64)v;
          int i = ++hsz;
          while (i > 1) {
            int par = i >> 1;
            if (heap[par] <= nk) break;
            heap[i] = heap[par]; i = par;
          }
          heap[i] = nk;
        }
      }
    }

    // initialize leaves
    for (int i = 1; i <= n; i++) {
      dsu[i] = i; sz[i] = 1; rep[i] = i;
      mn[i] = dist[i];
      val[i] = 0;
      up[0][i] = 0;
    }
    // order = identity
    for (int i = 0; i < m; i++) order[i] = i;

    // radix sort order[] by ea[] ascending (4 x 8-bit passes)
    {
      int *src = order, *dst = tmp;
      for (int shift = 0; shift < 32; shift += 8) {
        int cnt[256];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < m; i++) cnt[(ea[src[i]] >> shift) & 0xff]++;
        int sum = 0;
        for (int c = 0; c < 256; c++) { int t = cnt[c]; cnt[c] = sum; sum += t; }
        for (int i = 0; i < m; i++) dst[cnt[(ea[src[i]] >> shift) & 0xff]++] = src[i];
        int *t = src; src = dst; dst = t;
      }
      if (src != order) {
        for (int i = 0; i < m; i++) order[i] = tmp[i];
      }
    }

    // Kruskal reconstruction tree (edges descending by altitude)
    int tot = n;
    for (int idx = m - 1; idx >= 0; idx--) {
      int e = order[idx];
      u32 a = ea[e];
      int ru = find(eu[e]), rv = find(ev[e]);
      if (ru == rv) continue;
      ++tot;
      val[tot] = a;
      int t1 = rep[ru], t2 = rep[rv];
      up[0][t1] = tot;
      up[0][t2] = tot;
      u32 m1 = mn[t1], m2 = mn[t2];
      mn[tot] = (m1 < m2) ? m1 : m2;
      if (sz[ru] < sz[rv]) { int t = ru; ru = rv; rv = t; }
      dsu[rv] = ru; sz[ru] += sz[rv]; rep[ru] = tot;
    }
    up[0][tot] = 0; // root

    // binary lifting table
    for (int j = 1; j < LOG; j++) {
      int *cur = up[j], *prv = up[j - 1];
      for (int i = 1; i <= tot; i++) cur[i] = prv[prv[i]];
    }

    // queries
    u32 lastans = 0;
    u32 sp1 = S + 1;
    for (int q = 0; q < Q; q++) {
      int v0 = rd(), p0 = rd();
      int v = (int)(((long long)v0 + (K ? (long long)lastans : 0ll) - 1) % n) + 1;
      int p = (int)(((long long)p0 + (K ? (long long)lastans : 0ll)) % sp1);
      int cur = v;
      for (int j = LOG - 1; j >= 0; j--) {
        int anc = up[j][cur];
        if (anc && val[anc] > (u32)p) cur = anc;
      }
      lastans = mn[cur];
      put_u32(lastans);
    }
  }

  di->stdout_size = (u64)(op - di->stdout_ptr);

  // fast exit
  __asm__ __volatile__("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax", "rdi", "memory");
  __builtin_unreachable();
}

评测结果