第一个点是对的
然后后面很一致的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;
}