代码

// NOIP2018 旅行 (noip18d) - tight version.
//  * own __libc_start_main: no libc init, direct DuckInfo stdin/stdout access
//  * fast integer parsing / 2-digit-table output
//  * tree case: single greedy DFS
//  * base-ring case: cycle edge chosen in O(k) by a local-divergence scan;
//    the "counter-clockwise only" candidate is provably larger (after mirroring
//    ring[1] < ring[k-1]), so only ONE DFS is materialised.
#include <string.h>
#include <algorithm>
using namespace std;
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));

enum { MAXN = 100005, MAXM = 100005 };
static int EA[MAXM], EB[MAXM], cstart[MAXN], cto[2*MAXM];
static int visT[MAXN], dfsPar[MAXN], dfsPtr[MAXN], seqA[MAXN];
static char ringMark[MAXN];
static int ringOrd[MAXN], ringIdx[MAXN], wArr[MAXN], unwArr[MAXN], queueBuf[MAXN], degBuf[MAXN], parBFS[MAXN], posBuf[MAXN];

static int N, M;
static int visStamp = 0;

static const char DIG2[201] =
  "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
  "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
  "8081828384858687888990919293949596979899";

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

static inline char* putu(char *o, int x){
    char t[12]; int k=0;
    while(x >= 100){ int r = x - (x/100)*100; x /= 100; t[k++] = DIG2[2*r+1]; t[k++] = DIG2[2*r]; }
    if(x >= 10){ t[k++] = DIG2[2*x+1]; t[k++] = DIG2[2*x]; }
    else t[k++] = (char)('0'+x);
    while(k) *o++ = t[--k];
    return o;
}

static inline void isort(int *a, int n){
    for(int i=1;i<n;i++){ int x=a[i], j=i-1; while(j>=0 && a[j]>x){ a[j+1]=a[j]; j--; } a[j+1]=x; }
}

static void buildCSR(){
    memset(cstart, 0, sizeof(int)*(N+2));
    for(int i=0;i<M;i++){ cstart[EA[i]+1]++; cstart[EB[i]+1]++; }
    for(int i=1;i<=N+1;i++) cstart[i]+=cstart[i-1];
    memcpy(posBuf, cstart, sizeof(int)*(N+2));
    for(int i=0;i<M;i++){
        cto[posBuf[EA[i]]++] = EB[i];
        cto[posBuf[EB[i]]++] = EA[i];
    }
    for(int u=1;u<=N;u++){
        int s=cstart[u], len=cstart[u+1]-s;
        if(len<=1) continue;
        if(len<=32) isort(cto+s, len);
        else sort(cto+s, cto+s+len);
    }
}

static void genSeq(int bu, int bv, int *out){
    visStamp++;
    int cnt = 0;
    int u = 1;
    visT[1] = visStamp; out[cnt++] = 1; dfsPar[1] = 0; dfsPtr[1] = cstart[1];
    while(true){
        int i = dfsPtr[u], end = cstart[u+1], adv = 0;
        while(i < end){
            int v = cto[i++];
            if(visT[v] == visStamp) continue;
            if((u==bu && v==bv) || (u==bv && v==bu)) continue;
            dfsPtr[u] = i;
            visT[v] = visStamp; out[cnt++] = v; dfsPar[v] = u; dfsPtr[v] = cstart[v];
            u = v; adv = 1; break;
        }
        if(!adv){
            dfsPtr[u] = i;
            if(u == 1) break;
            u = dfsPar[u];
        }
    }
}

static void solve18d(){
    buildCSR();
    if(M == N-1){ genSeq(-1,-1,seqA); return; }
    memset(ringMark, 0, sizeof(char)*(N+1));
    for(int u=1;u<=N;u++) degBuf[u] = cstart[u+1]-cstart[u];
    int qh=0, qt=0;
    for(int i=1;i<=N;i++) if(degBuf[i]==1) queueBuf[qt++] = i;
    while(qh<qt){
        int u = queueBuf[qh++]; ringMark[u]=1;
        int *ce = cto + cstart[u], *ee = cto + cstart[u+1];
        for(; ce<ee; ce++){ int v=*ce; if(!ringMark[v] && --degBuf[v]==1) queueBuf[qt++]=v; }
    }
    visStamp++;
    int r = 0;
    qh=0; qt=0;
    queueBuf[qt++] = 1; visT[1] = visStamp; parBFS[1] = 0;
    while(qh<qt){
        int u = queueBuf[qh++];
        if(!ringMark[u]){ r = u; break; }
        int *ce = cto + cstart[u], *ee = cto + cstart[u+1];
        for(; ce<ee; ce++){ int v=*ce; if(visT[v]!=visStamp){ visT[v]=visStamp; parBFS[v]=u; queueBuf[qt++]=v; } }
    }
    if(!r) r = 1;
    int k = 0; ringOrd[k++] = r;
    {
        int prev = r, cur = -1;
        for(int i=cstart[r]; i<cstart[r+1]; i++) if(!ringMark[cto[i]]){ cur = cto[i]; break; }
        int guard = 0;
        while(cur != -1 && cur != r && guard++ <= N){
            ringOrd[k++] = cur;
            int *ce = cto + cstart[cur], *ee = cto + cstart[cur+1];
            int nxt = -1;
            for(; ce<ee; ce++){ int v=*ce; if(!ringMark[v] && v != prev){ nxt = v; break; } }
            prev = cur; cur = nxt;
        }
    }
    if(k >= 3 && ringOrd[1] > ringOrd[k-1]){
        for(int a=1,b=k-1;a<b;a++,b--){ int t=ringOrd[a]; ringOrd[a]=ringOrd[b]; ringOrd[b]=t; }
    }
    for(int i=1;i<=N;i++) ringIdx[i] = -1;
    for(int i=0;i<k;i++) ringIdx[ringOrd[i]] = i;
    for(int i=1;i+1<k;i++){
        int u = ringOrd[i], lim = ringOrd[i+1], best = 0x3f3f3f3f;
        int *ce = cto + cstart[u], *ee = cto + cstart[u+1];
        for(; ce<ee; ce++){ int v=*ce; if(ringIdx[v]>=0) continue; if(v>lim && v<best) best=v; }
        wArr[i] = best;
    }
    {
        int last = 0x3f3f3f3f;
        unwArr[1] = 0x3f3f3f3f;
        for(int i=1;i+1<k;i++){ if(wArr[i] < 0x3f3f3f3f) last = wArr[i]; unwArr[i+1] = last; }
    }
    int nextR = 0x3f3f3f3f;
    {
        int u = ringOrd[0], lim = ringOrd[1], pb = parBFS[u];
        int *ce = cto + cstart[u], *ee = cto + cstart[u+1];
        for(; ce<ee; ce++){
            int v = *ce;
            if(ringIdx[v] >= 0) continue;
            if(v == pb) continue;
            if(v > lim && v < nextR) nextR = v;
        }
        if(ringOrd[k-1] < nextR) nextR = ringOrd[k-1];
    }
    int best = k-1;
    for(int j=k-2;j>=1;j--){
        int vj;
        if(wArr[j] < 0x3f3f3f3f) vj = wArr[j];
        else if(unwArr[j] < 0x3f3f3f3f) vj = unwArr[j];
        else vj = nextR;
        if(vj < ringOrd[j+1]) best = j;
    }
    if(best == k-1) genSeq(ringOrd[k-1], ringOrd[0], seqA);
    else genSeq(ringOrd[best], ringOrd[best+1], seqA);
}

static inline void rx(){
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx","r11","memory");
    __builtin_unreachable();
}

#ifndef FUZZ
extern "C" int __libc_start_main(int (*m)(int,char**,char**), int argc, char **v,
                                 void (*i)(void), void (*f)(void), void (*l)(void)){
    char **env = v + argc + 1;
    while(*env) env++;
    u64 *a = (u64*)(env+1);
    DI *di = 0;
    for(; a[0]; a += 2) if(a[0] == 0x6b637564ULL){ di = (DI*)a[1]; break; }
    char *p = (char*)di->in;
    N = rd(p); M = rd(p);
    if(M > MAXM-2 || N > MAXN-2) rx();
    for(int i=0;i<M;i++){ EA[i] = rd(p); EB[i] = rd(p); }
    solve18d();
    char *o = di->out;
    for(int i=0;i<N;i++){
        o = putu(o, seqA[i]);
        *o++ = (i+1<N) ? ' ' : '\n';
    }
    di->outsz = (u64)(o - di->out);
    rx();
    return 0;
}
int main(){return 0;}
#endif

评测结果