代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;
typedef unsigned long u64;

#define MAXN 200005
#define MAXM 400005
#define MAXV 400010
#define MAXA 800010
#define LOG 19

typedef struct { u32 u, v, l, a; } Edge;
typedef struct { u32 to, next, w; } Arc;

static Edge edges[MAXM], tmp_edges[MAXM];
static Arc arcs[MAXA];
static u32 head[MAXN], radix_count[65536];
static u32 dsu[MAXV], up[LOG][MAXV];
static u64 dis[MAXV], best[MAXV];
static u32 height[MAXV];
static u32 heap[MAXN];
static int heap_pos[MAXN];

static __attribute__((always_inline)) inline u32 rd(const char **pp) {
    const char *p = *pp;
    while ((unsigned char)(*p - '0') > 9) ++p;
    u32 x = 0;
    do { x = x * 10u + (u32)(*p++ - '0'); }
    while ((unsigned char)(*p - '0') <= 9);
    *pp = p;
    return x;
}

static __attribute__((always_inline)) inline char *putu(char *p, u64 x) {
    char s[24]; u32 n = 0;
    do { s[n++] = (char)('0' + x % 10); x /= 10; } while (x);
    do { *p++ = s[--n]; } while (n);
    *p++ = '\n';
    return p;
}

static void radix_sort(u32 m) {
    Edge *src = edges, *dst = tmp_edges;
    for (u32 shift = 0; shift <= 16; shift += 16) {
        __builtin_memset(radix_count, 0, sizeof(radix_count));
        for (u32 i = 0; i < m; ++i) ++radix_count[(src[i].a >> shift) & 65535u];
        u32 sum = 0;
        for (u32 i = 0; i < 65536; ++i) {
            u32 c = radix_count[i]; radix_count[i] = sum; sum += c;
        }
        for (u32 i = 0; i < m; ++i)
            dst[radix_count[(src[i].a >> shift) & 65535u]++] = src[i];
        Edge *sw = src; src = dst; dst = sw;
    }
}

static __attribute__((always_inline)) inline void heap_swap(u32 i, u32 j) {
    u32 a = heap[i], b = heap[j]; heap[i] = b; heap[j] = a;
    heap_pos[a] = (int)j; heap_pos[b] = (int)i;
}

static __attribute__((always_inline)) inline void heap_up(u32 i) {
    while (i > 1) {
        u32 p = i >> 1;
        if (dis[heap[p]] <= dis[heap[i]]) break;
        heap_swap(p, i); i = p;
    }
}

static __attribute__((always_inline)) inline void heap_down(u32 i, u32 size) {
    for (;;) {
        u32 c = i << 1;
        if (c > size) break;
        if (c < size && dis[heap[c + 1]] < dis[heap[c]]) ++c;
        if (dis[heap[i]] <= dis[heap[c]]) break;
        heap_swap(i, c); i = c;
    }
}

static void dijkstra(u32 n) {
    const u64 inf = ~(u64)0 >> 2;
    for (u32 i = 1; i <= n; ++i) dis[i] = inf;
    __builtin_memset(heap_pos, 0, (n + 1) * sizeof(*heap_pos));
    u32 hs = 1; heap[1] = 1; heap_pos[1] = 1; dis[1] = 0;
    while (hs) {
        u32 u = heap[1], tail = heap[hs--];
        heap_pos[u] = -1;
        if (hs) { heap[1] = tail; heap_pos[tail] = 1; heap_down(1, hs); }
        for (u32 ei = head[u]; ei != ~0u; ei = arcs[ei].next) {
            u32 v = arcs[ei].to;
            u64 nd = dis[u] + arcs[ei].w;
            if (nd < dis[v]) {
                dis[v] = nd;
                int pos = heap_pos[v];
                if (!pos) { heap[++hs] = v; heap_pos[v] = (int)hs; heap_up(hs); }
                else if (pos > 0) heap_up((u32)pos);
            }
        }
    }
}

static __attribute__((always_inline)) inline u32 root(u32 x) {
    u32 r = x;
    while (dsu[r] != r) r = dsu[r];
    while (dsu[x] != x) { u32 y = dsu[x]; dsu[x] = r; x = y; }
    return r;
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *p = info->stdin_ptr;
    char *out = info->stdout_ptr;
    u32 T = rd(&p);
    while (T--) {
        u32 n = rd(&p), m = rd(&p);
        __builtin_memset(head, 0xff, (n + 1) * sizeof(*head));
        u32 ac = 0;
        for (u32 i = 0; i < m; ++i) {
            u32 u = rd(&p), v = rd(&p), l = rd(&p), a = rd(&p);
            edges[i] = (Edge){u, v, l, a};
            arcs[ac] = (Arc){v, head[u], l}; head[u] = ac++;
            arcs[ac] = (Arc){u, head[v], l}; head[v] = ac++;
        }
        if (n) dijkstra(n);
        radix_sort(m);
        __builtin_memset(up[0], 0, (2 * n + 1) * sizeof(**up));
        for (u32 i = 1; i <= n; ++i) dsu[i] = i, best[i] = dis[i], height[i] = ~0u;
        u32 tot = n;
        for (u32 ii = m; ii; --ii) {
            Edge e = edges[ii - 1];
            u32 x = root(e.u), y = root(e.v);
            if (x == y) continue;
            ++tot; dsu[tot] = tot; dsu[x] = dsu[y] = tot;
            up[0][x] = up[0][y] = tot;
            height[tot] = e.a;
            best[tot] = best[x] < best[y] ? best[x] : best[y];
        }
        for (u32 k = 1; k < LOG; ++k)
            for (u32 i = 1; i <= tot; ++i)
                up[k][i] = up[k - 1][up[k - 1][i]];

        u32 Q = rd(&p), K = rd(&p), S = rd(&p);
        u64 last = 0;
        for (u32 qi = 0; qi < Q; ++qi) {
            u64 v0 = rd(&p), p0 = rd(&p);
            u32 v = (u32)((v0 + (u64)K * last - 1) % n + 1);
            u32 water = (u32)((p0 + (u64)K * last) % ((u64)S + 1));
            for (int k = LOG - 1; k >= 0; --k) {
                u32 a = up[k][v];
                if (a && height[a] > water) v = a;
            }
            last = best[v]; out = putu(out, last);
        }
    }
    info->stdout_size = (u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果