代码

// noi18a 【NOI2018】归程 -- v4
// Kruskal tree -> DFS leaf order -> boundary array A0[b] = merge altitude at the boundary
// between DFS-adjacent leaves b,b+1.
// component(v,p) = maximal leaf interval around x=pos[v] whose internal boundaries all have
//                  A0 > p  (a boundary with A0 <= p blocks: its merging edge is flooded).
//   L = prevLE(x-1,p)+1,  R = nextLE(x,p),  answer = min dPos[L..R]
// Searches / range-min use SIMD scans over a 3-level 64-ary block structure.
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
typedef unsigned long long u64;
typedef unsigned int u32;
typedef long long i64;
static char g_in[80 << 20];
static char g_out[80 << 20];
#else
typedef unsigned long long u64;
typedef unsigned int u32;
typedef long long i64;
#endif
#include <immintrin.h>
#define PHASE_TIMING 1

#define MAXN 200005
#define MAXM 400005
#define MAXARC 800005
#define MAXND 400010
#define RBITS 10
#define RSIZE (1u << RBITS)
#define RMASK (RSIZE - 1)
#define SH1 6
#define MSK1 63
#define MAXB1 (MAXN / 64 + 2)
#define MAXB2 (MAXB1 / 64 + 2)

static u32 eln[MAXM];   // the ONLY one of the four the parser still needs: adj packs (node, w)
static u32 rka[MAXM], rkb[MAXM];
static u32 beg[MAXN + 2], curs[MAXN + 2], cnt[RSIZE + 1];
static u32 adj[MAXARC];
static u32 sz[MAXND];
static u32 dist_[MAXN + 2];
static u64 heapp[MAXARC + 8];
// ---- DIAL'S BUCKET QUEUE (replaces the radix heap) ----
// Weights are packed in 14 bits (`adj` = v | (w<<18), w = a>>18 < 2^14), so maxw <= 16383.
// THE WHOLE RADIX REDISTRIBUTION IS UNNECESSARY: a monotone bucket queue whose width W
// exceeds maxw extracts keys in non-decreasing order with ZERO re-bucketing.
//   * a node is stored as its VERTEX ONLY (4 B, not 12) and its key is read from dist_ at pop;
//   * all live keys lie in [cb*W, cb*W + maxw + W), a span of <= 5 buckets, so a 16-slot ring is
//     collision-free and the cursor advances at most 5 slots per pop;
//   * a new key is >= the current bucket's base (relaxation uses dist_[u] >= cb*W), so the
//     cursor can never step past a live entry.
#define DBITS 12
#define DWIDTH (1u << DBITS)
#define DRING 16
#define DMASK (DRING - 1)
#define DNIL 0xFFFFFFFFu
static u32 dhead[DRING];
static u32 dtag[DRING];
/* POOL CAPACITY.  `d_np` is UNBOUNDED and `d_pool`/`d_nx`/`d_key` are followed in .bss by
   dtag/dhead/dist_ -- so an over-run corrupts the cursor tags and the distance array
   rather than faulting.  4x the previous 2*MAXARC+16. */
#define DPOOL (8 * MAXARC + 64)
static u32 d_pool[DPOOL];
static u32 d_nx[DPOOL];
/* THE STALE KEY.  `d_pool` stores the VERTEX only, so a pop cannot tell a live entry
   from a stale one and MUST re-scan the vertex's whole adjacency list.  For a degree-D
   hub relaxed K times that is K*D arc visits instead of D: measured 29x slower on an
   adversarial hub graph (0.027 s -> 0.820 s) and it is the `+6 ms on small cases`
   symptom on the board.  This is the radix heap's `if (d > dist_[u]) continue;` -- the
   bucket test `(d>>DBITS) < d_cb` does NOT work, because a hub's stale entries share a
   bucket with its live one. */
static u32 d_key[DPOOL];
static u32 d_np, d_cb, d_cnt, d_lastkey;
__attribute__((always_inline)) static inline void dial_push(u32 v) {
  u32 b = dist_[v] >> DBITS;
  u32 i = b & DMASK;
  if (dtag[i] != b) { dtag[i] = b; dhead[i] = DNIL; }
  u32 ni = d_np++;
  d_pool[ni] = v; d_key[ni] = dist_[v]; d_nx[ni] = dhead[i]; dhead[i] = ni;
  d_cnt++;
}
// BOUNDED pop.  The cursor walk MUST NOT be an unbounded `for(;;)`: if an entry ever
// ends up behind the cursor the unbounded form walks 2^32 buckets (~1.4-4 s, which the
// judge reports as RE/Time).  This form inspects at most DRING slots, so it cannot spin,
// and it recovers the true minimum tag over ALL slots -- including one behind the cursor.
__attribute__((always_inline)) static inline u32 dial_pop(void) {
  u32 i = d_cb & DMASK;
  if (dtag[i] != d_cb || dhead[i] == DNIL) {
    u32 best = 0xFFFFFFFFu, bi = 0;
    for (u32 s = 0; s < DRING; s++) {
      u32 j = (d_cb + s) & DMASK;
      if (dhead[j] != DNIL && dtag[j] < best) { best = dtag[j]; bi = j; }
    }
    if (best == 0xFFFFFFFFu) { d_cnt = 0; return 1u; }   // unreachable; fail safe, never spin
    d_cb = best; i = bi;
  }
  u32 n = dhead[i]; dhead[i] = d_nx[n]; d_cnt--;
  d_lastkey = d_key[n];
  return d_pool[n];
}
static u32 dsu[MAXND], alt_[MAXND], ch1[MAXND], ch2[MAXND], Rr[MAXND];
static u32 stk[MAXND];
static u32 posOf[MAXN + 2];
static u32 leafOf[MAXN];      /* DFS position -> vertex (posOf's inverse) */
/* (pos, zeroAlt[pos]) PACKED per VERTEX: the query's serial dependency chain becomes ONE load,
   and zeroAlt[] disappears entirely.  vinfo[v] lo32 = posOf[v], hi32 = zeroAlt[posOf[v]]. */
static u64 vinfo[MAXN + 2];
static u32 dPos[MAXN];
static u32 A0[MAXN];
static u32 L1A[MAXB1], L2A[MAXB2];
static u32 L1D[MAXB1], L2D[MAXB2];
static u32 MB, nb1, nb2, nn;
struct KRRec { u32 key; u32 u; u32 v; };            /* key = ~eal : descending altitude */
static KRRec krs[2][MAXM];

#ifdef PHASE_TIMING
#include <cstdio>
static u64 ph[16];
static inline u64 rd() { return __builtin_ia32_rdtsc(); }
#define PH_START() u64 _t = rd()
#define PH_MARK(i) do { u64 _n = rd(); ph[i] += _n - _t; _t = _n; } while (0)
#define PH_DUMP() do { for (int _i = 0; _i < 16; _i++) if (ph[_i]) fprintf(stderr, "phase %d: %llu cycles\n", _i, (unsigned long long)ph[_i]); } while (0)
#else
#define PH_START()
#define PH_MARK(i)
#define PH_DUMP()
#endif

#ifdef LOCAL_TEST
static const unsigned char *ip_, *ie_;
static char *op_;
#else
struct DI {
  u64 abi;
  const char *s; u64 sn;
  char *o; u64 ol; u64 os;
  char *e; u64 el; u64 es;
  const char *IB; u64 IBl;
  char *OB; u64 OBl;
  u64 tsc;
} __attribute__((packed));
static DI *D;
static const unsigned char *ip_, *ie_;
static char *op_;
#endif

static inline u32 ni() {
  const unsigned char *p = ip_;
  while (*p <= ' ') p++;
  u32 v = (u32)(*p++ - '0');
  while (*p > ' ') v = v * 10 + (u32)(*p++ - '0');
  ip_ = p;
  return v;
}

static const char D2[] =
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899";

static inline void pu32(u32 v) {
  char t[12];
  int q = 0;
  while (v >= 100) {
    u32 d = v / 100, r = (v - d * 100) * 2;
    v = d;
    t[q++] = D2[r + 1]; t[q++] = D2[r];
  }
  if (v >= 10) { u32 r = v * 2; t[q++] = D2[r + 1]; t[q++] = D2[r]; }
  else t[q++] = (char)('0' + v);
  char *o = op_;
  while (q) *o++ = t[--q];
  op_ = o;
}

// ---- SIMD scans (AVX2; see mk_qavx.py for why each shape was chosen) ----
#pragma GCC push_options
#pragma GCC target("avx2")
static inline int scanLeftLE(const u32 *arr, int lo, int hi, u32 p) {
  __m256i vp = _mm256_set1_epi32((int)p);
  int j = hi;
  while (j - 7 >= lo) {
    __m256i x = _mm256_loadu_si256((const __m256i *)(arr + j - 7));
    u32 bits = (~(u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x, vp)))) & 0xFFu;
    if (bits) return j - 7 + (31 - __builtin_clz(bits));
    j -= 8;
  }
  for (; j >= lo; j--) if (arr[j] <= p) return j;
  return -1;
}
static inline int scanRightLE(const u32 *arr, int lo, int hi, u32 p) {
  __m256i vp = _mm256_set1_epi32((int)p);
  int j = lo;
  while (j + 7 <= hi) {
    __m256i x = _mm256_loadu_si256((const __m256i *)(arr + j));
    u32 bits = (~(u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(x, vp)))) & 0xFFu;
    if (bits) return j + __builtin_ctz(bits);
    j += 8;
  }
  for (; j <= hi; j++) if (arr[j] <= p) return j;
  return hi + 1;
}
// ONE horizontal reduction for the whole block, not one per 8 elements.
static inline u32 scanMin(const u32 *arr, int lo, int hi) {
  __m256i vmin = _mm256_set1_epi32(0x7FFFFFFF);
  int j = lo;
  while (j + 7 <= hi) {
    vmin = _mm256_min_epi32(vmin, _mm256_loadu_si256((const __m256i *)(arr + j)));
    j += 8;
  }
  __m128i mn = _mm_min_epi32(_mm256_castsi256_si128(vmin), _mm256_extracti128_si256(vmin, 1));
  mn = _mm_min_epi32(mn, _mm_shuffle_epi32(mn, 0x4E));
  mn = _mm_min_epi32(mn, _mm_shuffle_epi32(mn, 0xB1));
  u32 m = (u32)_mm_cvtsi128_si32(mn);
  for (; j <= hi; j++) if (arr[j] < m) m = arr[j];
  return m;
}
static inline int min2(int a, int b) { return a < b ? a : b; }
__attribute__((noinline)) static int prevLE(u32 i, u32 p) {
  int i0 = (int)i;
  int mb = (int)MB - 1;
  int r = scanLeftLE(A0, i0 & ~MSK1, i0, p);
  if (r >= 0) return r;
  int j = (i0 >> SH1) - 1;
  if (j < 0) return -1;
  r = scanLeftLE(L1A, j & ~MSK1, j, p);
  if (r >= 0) return scanLeftLE(A0, r << SH1, min2((r << SH1) + MSK1, mb), p);
  int g = (j >> SH1) - 1;
  if (g < 0) return -1;
  r = scanLeftLE(L2A, 0, g, p);
  if (r < 0) return -1;
  int r1 = scanLeftLE(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
  if (r1 < 0) return -1;
  return scanLeftLE(A0, r1 << SH1, min2((r1 << SH1) + MSK1, mb), p);
}
__attribute__((noinline)) static int nextLE(u32 i, u32 p) {
  int i0 = (int)i;
  int mb = (int)MB - 1;
  int hi = min2((i0 & ~MSK1) + MSK1, mb);
  int r = scanRightLE(A0, i0, hi, p);
  if (r <= hi) return r;
  int j = (i0 >> SH1) + 1;
  if (j >= (int)nb1) return (int)MB;
  int h1 = min2((j & ~MSK1) + MSK1, (int)nb1 - 1);
  r = scanRightLE(L1A, j, h1, p);
  if (r <= h1) return scanRightLE(A0, r << SH1, min2((r << SH1) + MSK1, mb), p);
  int g = (j >> SH1) + 1;
  if (g >= (int)nb2) return (int)MB;
  r = scanRightLE(L2A, g, (int)nb2 - 1, p);
  if (r > (int)nb2 - 1) return (int)MB;
  int r1 = scanRightLE(L1A, r << SH1, min2((r << SH1) + MSK1, (int)nb1 - 1), p);
  if (r1 > (int)nb1 - 1) return (int)MB;
  return scanRightLE(A0, r1 << SH1, min2((r1 << SH1) + MSK1, mb), p);
}
__attribute__((noinline)) static u32 rangeMin(u32 l, u32 r) {
  if (l == r) return dPos[l];                       // single-leaf component: no scan at all
  int bl = (int)(l >> SH1), br = (int)(r >> SH1);
  if (bl == br) return scanMin(dPos, (int)l, (int)r);
  u32 m = scanMin(dPos, (int)l, min2((bl << SH1) + MSK1, (int)nn - 1));
  u32 t = scanMin(dPos, br << SH1, (int)r);
  if (t < m) m = t;
  if (bl + 1 > br - 1) return m;
  int gl = (bl + 1) >> SH1, gr = (br - 1) >> SH1;
  if (gl == gr) { t = scanMin(L1D, bl + 1, br - 1); if (t < m) m = t; return m; }
  t = scanMin(L1D, bl + 1, min2((gl << SH1) + MSK1, (int)nb1 - 1)); if (t < m) m = t;
  t = scanMin(L1D, gr << SH1, br - 1); if (t < m) m = t;
  if (gl + 1 <= gr - 1) { t = scanMin(L2D, gl + 1, gr - 1); if (t < m) m = t; }
  return m;
}
#pragma GCC pop_options

// radix sort of FUSED edge records: every access is sequential.  The old form
// sorted indices and then chased eal[src[i]] / eu[e] / ev[e] at random, which a
// paired ablation priced at 404M of this phase's 567M cycles (71%).
static const KRRec *kruskal_sort(u32 m) {
  // krs[0] was filled BY THE PARSER (see solve()); nothing to copy here.
  KRRec *src = krs[0], *dst = krs[1];
  for (int pass = 0; pass < 3; pass++) {
    u32 shift = (u32)pass * RBITS;
    for (u32 j = 0; j < RSIZE; j++) cnt[j] = 0;
    for (u32 i = 0; i < m; i++) cnt[(src[i].key >> shift) & RMASK]++;
    u32 s = 0;
    for (u32 i = 0; i < RSIZE; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
    for (u32 i = 0; i < m; i++) { KRRec r = src[i]; dst[cnt[(r.key >> shift) & RMASK]++] = r; }
    KRRec *t = src; src = dst; dst = t;
  }
  return src;
}

static u32 find_(u32 x) {
  while (dsu[x] != x) { dsu[x] = dsu[dsu[x]]; x = dsu[x]; }
  return x;
}


// --- ARM fastmod: the query decode did two 64-bit `%` with RUNTIME divisors per query, which a
// timing-only ablation priced at 30-45 cycles of the 106-117-cycle decode (~35 % of it, ~3 % of the
// row).  Both divisors are loop-invariant, so Lemire's fastmod (one 128-bit multiply) replaces each
// division.  Exact for every x < 2^64 and d < 2^63; one conditional correction.
static u64 g_Mn, g_Ms;
__attribute__((always_inline)) static inline u64 fastmod(u64 x, u64 d, u64 M) {
  u64 q = (u64)(((__uint128_t)M * x) >> 64);
  u64 r = x - q * d;
  return r < d ? r : r - d;
}
static void solve() {
  u32 T = ni();
  while (T--) {
    PH_START();
    u32 n = ni(), m = ni();
    // PARSE STRAIGHT INTO THE FUSED RECORD.  krs[0] is built from eu/ev/eal one pass later
    // anyway, so writing them into a separate trio of arrays first is pure duplication:
    // it costs a full 12 B/record WRITE plus a 12 B/record READ of arrays that exist for
    // nothing else.  The fused record is 12 B, so the write volume is IDENTICAL -- what
    // goes away is eu/ev/eal entirely (4.7 MB of touched .bss) and one whole pass.
    // ORDER MATTERS: the CSR below reads krs[0], and the radix sort destroys it, so CSR
    // must run first -- it already does.
    for (u32 i = 0; i < m; i++) { krs[0][i].u = ni(); krs[0][i].v = ni(); eln[i] = ni(); krs[0][i].key = ~ni(); }
    u32 Q = ni(), K = ni(), S = ni();
    PH_MARK(0);

    // ---- CSR ----
    for (u32 i = 1; i <= n; i++) beg[i] = 0;
    for (u32 i = 0; i < m; i++) { beg[krs[0][i].u]++; beg[krs[0][i].v]++; }
    {
      u32 s = 0;
      for (u32 i = 1; i <= n; i++) { u32 c = beg[i]; beg[i] = s; curs[i] = s; s += c; }
      beg[n + 1] = s; curs[n + 1] = s;
      for (u32 i = 0; i < m; i++) {
        u32 a = krs[0][i].u, b = krs[0][i].v, w = eln[i];
        u32 pi = curs[a]++; adj[pi] = b | (w << 18);
        u32 pj = curs[b]++; adj[pj] = a | (w << 18);
      }
    }
    PH_MARK(1);

    // ---- Dijkstra from 1 ----
    const u32 INF = 3000000000u;
    for (u32 i = 1; i <= n; i++) dist_[i] = INF;
    dist_[1] = 0;
    {
      d_np = 0; d_cb = 0; d_cnt = 0;
      for (u32 k = 0; k < DRING; k++) { dhead[k] = DNIL; dtag[k] = 0xFFFFFFFFu; }
      dial_push(1);
      while (d_cnt) {
        u32 u = dial_pop();
        if (d_lastkey != dist_[u]) continue;   // stale entry: skip, as the radix heap does
        u32 d = dist_[u];
        u32 e = beg[u], e2 = beg[u + 1];
        for (; e < e2; e++) {
          u32 a = adj[e];
          u32 v = a & 262143u;
          u32 nd = d + (a >> 18);
          if (nd < dist_[v]) { dist_[v] = nd; dial_push(v); }
        }
      }
    }
    PH_MARK(2);

    // ---- KRT ----
    for (u32 i = 1; i <= n; i++) { dsu[i] = i; alt_[i] = 0xFFFFFFFFu; }
    u32 N = n;
    if (m) {
      const KRRec *rs = kruskal_sort(m);
      for (u32 i = 0; i < m; i++) {
        u32 a = find_(rs[i].u), b = find_(rs[i].v);
        if (a != b) {
          u32 w = ++N;
          ch1[w] = a; ch2[w] = b;
          alt_[w] = ~rs[i].key;
          dsu[a] = w; dsu[b] = w; dsu[w] = w;
        }
      }
    }
    PH_MARK(3);

    // ---- DFS leaf order + boundary array ----
    {
      u32 sp = 0;
      stk[sp++] = N;
      u32 c = 0;
      while (sp) {
        u32 u = stk[--sp];
        if (u <= n) {
          posOf[u] = c;
          leafOf[c] = u;
          dPos[c] = dist_[u];
          Rr[u] = c;
          c++;
        } else {
          stk[sp++] = ch2[u]; stk[sp++] = ch1[u];
        }
      }
    }
    for (u32 u = 1; u <= n; u++) sz[u] = 1;
    for (u32 u = n + 1; u <= N; u++) {
      sz[u] = sz[ch1[u]] + sz[ch2[u]];
      Rr[u] = Rr[ch2[u]];
      A0[Rr[ch1[u]]] = alt_[u];
    }
    // zeroAlt[pos] = altitude of LCA(leaf at pos, leaf of vertex 1); +inf if pos == pos1
    {
      /* The ranges below cover EVERY position except pos1, whose only vertex is v=1 (leafOf[pos1]==1).
         So one store seeds it and no full-array init pass is needed.  posOf[leafOf[i]] == i, so the
         packed word is built with no extra load and no read-modify-write. */
      u32 pos1 = posOf[1];
      vinfo[1] = (0xFFFFFFFFull << 32) | (u64)pos1;
      u32 u = N;
      while (u > n) {
        u32 c1 = ch1[u], c2 = ch2[u];
        if (pos1 <= Rr[c1]) {
          u32 hi = Rr[c2], lo = hi - sz[c2] + 1;
          for (u32 i = lo; i <= hi; i++) { u32 v = leafOf[i]; vinfo[v] = ((u64)alt_[u] << 32) | (u64)i; }
          u = c1;
        } else {
          u32 hi = Rr[c1], lo = hi - sz[c1] + 1;
          for (u32 i = lo; i <= hi; i++) { u32 v = leafOf[i]; vinfo[v] = ((u64)alt_[u] << 32) | (u64)i; }
          u = c2;
        }
      }
    }
    PH_MARK(4);

    // ---- block minima ----
    nn = n; MB = n - 1;
    nb1 = (MB + MSK1) >> SH1;
    nb2 = (nb1 + MSK1) >> SH1;
    {
      for (u32 j = 0; j < nb1; j++) {
        u32 lo = j << SH1, hi = lo + MSK1;
        u32 hiA = hi; if (hiA >= MB) hiA = MB - 1;
        L1A[j] = scanMin(A0, (int)lo, (int)hiA);
        u32 loD = lo; if (loD >= n) loD = n - 1;
        u32 hiD = hi; if (hiD >= n) hiD = n - 1;
        L1D[j] = scanMin(dPos, (int)loD, (int)hiD);
      }
      for (u32 j = 0; j < nb2; j++) {
        u32 lo = j << SH1, hi = lo + MSK1;
        if (hi >= nb1) hi = nb1 - 1;
        L2A[j] = scanMin(L1A, (int)lo, (int)hi);
        L2D[j] = scanMin(L1D, (int)lo, (int)hi);
      }
    }
    PH_MARK(5);

    g_Mn = (u64)(~0ull / (u64)n) + 1; g_Ms = (u64)(~0ull / ((u64)S + 1)) + 1;
    // ---- queries ----
    i64 lastans = 0;
    for (u32 qi = 0; qi < Q; qi++) {
      u32 v0 = ni(), p0 = ni();
      u64 la = (u64)lastans;
      u32 v = (u32)fastmod((u64)(v0 - 1) + (u64)K * la, (u64)n, g_Mn) + 1;
      u32 p = (u32)fastmod((u64)p0 + (u64)K * la, (u64)S + 1, g_Ms);
      u64 vi = vinfo[v];
      u32 x = (u32)vi;
      u32 ans;
      if ((u32)(vi >> 32) > p) {
        ans = 0;
      } else {
        _mm_prefetch((const char *)(A0 + (x & ~MSK1)), _MM_HINT_T0);
        u32 Lb = (x == 0) ? 0 : (u32)(prevLE(x - 1, p) + 1);
        u32 Rb = (x >= MB) ? (n - 1) : (u32)nextLE(x, p);
        ans = rangeMin(Lb, Rb);
      }
      lastans = (i64)ans;
      pu32(ans); *op_++ = '\n';
    }
    PH_MARK(6);
  }
}

#ifdef LOCAL_TEST
int main() {
  size_t sn = fread(g_in, 1, sizeof(g_in), stdin);
  ip_ = (const unsigned char *)g_in; ie_ = ip_ + sn;
  op_ = g_out;
  solve();
  fwrite(g_out, 1, (size_t)(op_ - g_out), stdout);
  PH_DUMP();
  return 0;
}
#else
int main() { return 0; }
extern "C" void __libc_start_main(void *mmm, int argc, char **argv) {
  (void)mmm;
  unsigned long *p = (unsigned long *)(argv + argc + 1);
  while (*p) p++;
  p++;
  for (; p[0]; p += 2) if (p[0] == 0x6b637564UL) { D = (DI *)p[1]; break; }
  if (D) {
    ip_ = (const unsigned char *)D->s; ie_ = ip_ + D->sn; op_ = D->o;
    solve();
    D->os = (u64)(op_ - D->o);
  }
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;);
}
#endif

评测结果