5分屎山求条喵
查看原帖
5分屎山求条喵
374452
AnteAntibe楼主2024/11/24 11:16

第一个点是对的
然后后面很一致的Too short on line1
看了一圈讨论班没有五分,可能是很怪异的错误呢)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e6 + 11;
char in[N];
ll n ,siz[N] ,f[N] ,vis[N];;

struct Adowashi{
    ll ch[30];
    ll len ,fa;
} sam[N];

ll las=1 ,tot=1;

void add(ll c) {
    ll p = las ,np ,q ,nq;
    np = ++tot;
    las = np;
    sam[np].len = sam[p].len + 1;
    f[tot] = siz[tot] = 1;
    for (;p && !sam[p].ch[c] ;p = sam[p].fa) {
        sam[p].ch[c] = np;
    }
    if (p == 0) {
        sam[np].fa = 1;
    }
    else {
        q = sam[p].ch[c];
        if (sam[q].len == sam[p].len + 1) {
            sam[np].fa = q;
        }
        else {
            //devide
            nq = ++tot;
            sam[nq] = sam[q];
            sam[nq].len = sam[p].len + 1;
            sam[q].fa = nq;
            sam[np].fa = nq;
            for (;p && sam[p].ch[c] == q ;p = sam[p].fa) {
                sam[p].ch[c] = nq;
            }
        }
    }
}

struct zxm{
    ll to ,nxt;
}es[N];
ll hd[N] ,idx;

void link(ll u ,ll v) {
    es[++idx].to = v;
    es[idx].nxt = hd[u];
    hd[u] = idx;
}

void dfs_siz(ll x) {
    for (ll i = hd[x] ;i ;i = es[i].nxt) {
        ll v = es[i].to;
        dfs_siz(v);
        siz[x] += siz[v];
    }
    f[x] = siz[x];
}

ll dfs_f (ll x) {
    if (vis[x]) {
        return f[x];
    }
    vis[x] = 1;
    for (ll i=0; i<26 ;i++) {
        ll v = sam[x].ch[i];
        if (v) {
            f[x] += dfs_f(v);
        }
    }
    return f[x];
}

void query(ll x ,ll rk) {
    if (rk > f[x]) {
        printf("-1");
        return;
    }
    if (rk <= siz[x]) {
        return;
    }
    rk -= siz[x];
    for (ll i=0 ;i<26 ;i++) {
        ll v = sam[x].ch[i];
        if (rk <= f[v]) {
            printf("%c" ,'a' + i);
            query(v ,rk);
            return;
        }
        else {
            rk -= siz[v];
        }
    }
}

void work(ll op ,ll rk) {
    if (op == 1ll) {
        dfs_siz(1);
    }
    else {
        for (ll i=2 ;i<=tot ;i++) {
            f[i] = siz[i] = 1;
        }
    }
    f[1] = siz[1] = 0;
    dfs_f(1);
    query(1ll ,rk);
}

ll op ,rk;
int main() {
    scanf("%s" ,in+1);
    n = strlen(in+1);
    for (ll i=1 ;i<=n ;i++) {
        char thi = in[i];
        add(thi - 'a');
    }
    for (ll i=2 ;i<=tot ;i++) {
        link(sam[i].fa ,i);
    }
    scanf("%lld %lld" ,&op ,&rk);
    work(op ,rk);
    return 0;
}
2024/11/24 11:16
加载中...