代码

/* NOI 2019 route -- time-bucketed convex hull DP.
 * Judge Duck exposes stdin/stdout as memory buffers through its aux vector.
 */
typedef unsigned long u64;
typedef long i64;

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#endif

typedef struct {
    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)) DuckInfo;

typedef struct {
    int a;                         /* source, then previous hull node */
    int b;                         /* destination, then next hull node */
    int q;
    int link;                      /* departure/arrival bucket link */
    i64 f;
} Edge;

enum { MAX_N = 100000, MAX_M = 1000000, MAX_T = 1000 };
static Edge e[MAX_M + 1];
static int depart[MAX_T + 1], arrive[MAX_T + 1];
static int hull_head[MAX_N + 1], hull_tail[MAX_N + 1];
static i64 coef_a, coef_b, coef_c;

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

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

static __attribute__((always_inline)) inline i64 line_y(int node) {
    Edge *x = &e[node - 1];
    return x->f + coef_a * x->q * x->q - coef_b * x->q;
}

static __attribute__((always_inline)) inline i64 eval(int node, int time) {
    Edge *x = &e[node - 1];
    return line_y(node) - 2 * coef_a * time * x->q;
}

static __attribute__((always_inline)) inline void insert_line(int station, int node) {
    Edge *z = &e[node - 1];
    int tail = hull_tail[station];
    if (tail && e[tail - 1].q == z->q) {
        if (line_y(tail) <= line_y(node)) return;
        tail = e[tail - 1].a;
        hull_tail[station] = tail;
        if (tail) e[tail - 1].b = 0;
        else hull_head[station] = 0;
    }
    while (tail) {
        int prev = e[tail - 1].a;
        if (!prev) break;
        i64 y0 = line_y(prev), y1 = line_y(tail), y2 = line_y(node);
        int x0 = e[prev - 1].q, x1 = e[tail - 1].q, x2 = z->q;
        if ((__int128)(y1 - y0) * (x2 - x1) <
            (__int128)(y2 - y1) * (x1 - x0)) break;
        tail = prev;
        hull_tail[station] = tail;
        e[tail - 1].b = 0;
    }
    z->a = tail;
    z->b = 0;
    if (tail) e[tail - 1].b = node;
    else hull_head[station] = node;
    hull_tail[station] = node;
}

static __attribute__((always_inline)) inline i64 query(int station, int time) {
    int h = hull_head[station];
    if (!h) return (i64)0x3fffffffffffffffL;
    int nx;
    while ((nx = e[h - 1].b) && eval(nx, time) <= eval(h, time)) h = nx;
    hull_head[station] = h;
    e[h - 1].a = 0;
    return eval(h, time);
}

static __attribute__((always_inline)) inline char *write_i64(char *out, i64 x) {
    char tmp[24];
    unsigned n = 0;
    if (x < 0) *out++ = '-', x = -x;
    do tmp[n++] = (char)('0' + x % 10), x /= 10; while (x);
    while (n) *out++ = tmp[--n];
    *out++ = '\n';
    return out;
}

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

int main(long argc, char **argv) {
#ifdef LOCAL
    (void)argc; (void)argv;
    static char local_in[16000000], local_out[64];
    u64 local_size = (u64)fread(local_in, 1, sizeof local_in, stdin);
    DuckInfo local_info = {0};
    local_info.stdin_ptr = local_in; local_info.stdin_size = local_size;
    local_info.stdout_ptr = local_out; local_info.stdout_limit = sizeof local_out;
    DuckInfo *info = &local_info;
#else
    DuckInfo *info = duck_info(argc, argv);
#endif
    const char *in = info->stdin_ptr;
    int n = (int)rd(&in), m = (int)rd(&in);
    coef_a = rd(&in); coef_b = rd(&in); coef_c = rd(&in);
    for (int i = 0; i < m; ++i) {
        int u = (int)rd(&in), v = (int)rd(&in);
        int p = (int)rd(&in), q = (int)rd(&in);
        e[i].a = u; e[i].b = v; e[i].q = q;
        e[i].link = depart[p];
        depart[p] = i + 1;
    }

    /* Synthetic arrival at station 1, time 0, with zero cost. */
    e[m].q = 0; e[m].f = 0;
    insert_line(1, m + 1);

    i64 answer = (i64)0x3fffffffffffffffL;
    for (int t = 0; t <= MAX_T; ++t) {
        int node = arrive[t];
        while (node) {
            Edge *x = &e[node - 1];
            int nx = x->link;
            int station = x->b;
            insert_line(station, node);
            node = nx;
        }
        node = depart[t];
        while (node) {
            Edge *x = &e[node - 1];
            int nx = x->link;
            int u = x->a, v = x->b, q = x->q;
            i64 best = query(u, t);
            if (best != (i64)0x3fffffffffffffffL) {
                x->f = best + coef_a * t * t + coef_b * t + coef_c;
                if (v == n && x->f + q < answer) answer = x->f + q;
                x->link = arrive[q];
                arrive[q] = node;
            }
            node = nx;
        }
    }
    char *out = info->stdout_ptr;
    char *end = write_i64(out, answer);
    info->stdout_size = (u64)(end - out);
#ifdef LOCAL
    fwrite(out, 1, info->stdout_size, stdout);
    return 0;
#else
    duck_exit();
#endif
}

评测结果