RT,WA 40pts,rec: https://www.luogu.com.cn/record/33766607
Detail:
#2,6,7,8,9: read'1',expected'....'
#5: Too short on line 1.
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
const int L = 1e6 + 5;
namespace SAM {
const int T = L << 1;
struct Node {
map<int, int> ch;
int link, len;
int max, min;
} t[T];
int last;
int total;
inline void extend(int c) {
int p = last, np = last = ++total;
t[np].len = t[p].len + 1;
for (; p && !t[p].ch.count(c); p = t[p].link)
t[p].ch[c] = np;
if (!p) {
t[np].link = 1;
} else {
int q = t[p].ch[c];
if (t[q].len == t[p].len + 1) {
t[np].link = q;
} else {
int nq = ++total;
t[nq].ch = t[q].ch, t[nq].link = t[q].link;
t[nq].len = t[p].len + 1;
t[q].link = t[np].link = nq;
while (p && t[p].ch.count(c) && t[p].ch[c] == q)
t[p].ch[c] = nq, p = t[p].link;
}
}
}
void init(int* b, int* e) {
last = total = 1;
for (register int* p = b + 1; p != e; p++)
extend(*p - *(p - 1));
for (register int i = 1; i <= total; i++)
t[i].min = t[i].len;
}
int b[T], c[T];
void topo_sort() {
for (register int i = 1; i <= total; i++) ++c[t[i].len];
for (register int i = 1; i <= total; i++) c[i] += c[i - 1];
for (register int i = 1; i <= total; i++) b[c[t[i].len]--] = i;
}
void scan(int* b, int* e);
int get_LCS();
};
void SAM::scan(int* b, int* e) {
int x = 1, len = 0;
for (register int* p = b + 1; p != e; p++) {
int c = *p - *(p - 1);
for (; x && !t[x].ch.count(c); x = t[x].link, len = t[x].len);
if (x) ++len, x = t[x].ch[c], t[x].max = max(t[x].max, len);
else x = 1, len = 0;
}
for (register int i = total; i; i--) {
int x = b[i], f = t[x].link;
t[f].max = max(t[f].max, t[x].max);
t[f].max = min(t[f].max, t[f].len);
}
for (register int i = 1; i <= total; i++)
t[i].min = min(t[i].min, t[i].max), t[i].max = 0;
}
int SAM::get_LCS() {
int ans = 0;
for (register int i = 1; i <= total; i++)
ans = max(ans, t[i].min);
return ans;
}
int dat[L];
signed main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (register int i = 1; i <= m; i++)
cin >> dat[i];
SAM::init(dat + 1, dat + 1 + m);
SAM::topo_sort();
while (--n) {
cin >> m;
for (register int i = 1; i <= m; i++)
cin >> dat[i];
if (m == 1) continue;
SAM::scan(dat + 1, dat + 1 + m);
}
cout << SAM::get_LCS() + 1 << endl;
return 0;
}
希望别无意义回复吧。。