QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562956 | #3844. LCS Spanning Tree | AmiyaCast | RE | 1ms | 7944kb | C++14 | 2.9kb | 2024-09-13 23:29:47 | 2024-09-13 23:29:47 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,b,a) for(int i=b;i>=a;--i)
const ll inf = 1145141919810;
using namespace std;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
inline void print(ll x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
return ;
}
inline void pprint(ll x){print(x); puts("");}
struct SA {
int n;
vector<int> sa, rk, h;
SA(const string &s) {
n = s.length();
sa.resize(n);
h.resize(n - 1);
rk.resize(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), [&](int a, int b) {
return s[a] < s[b];
});
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
}
int k = 1;
vector<int> tmp, cnt(n);
tmp.reserve(n);
while (rk[sa[n - 1]] < n - 1) {
tmp.clear();
for (int i = 0; i < k; ++i) {
tmp.push_back(n - k + i);
}
for (auto i : sa) {
if (i >= k) {
tmp.push_back(i - k);
}
}
fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; ++i) {
++cnt[rk[i]];
}
for (int i = 1; i < n; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
sa[--cnt[rk[tmp[i]]]] = tmp[i];
}
swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
}
k *= 2;
}
for (int i = 0, j = 0; i < n; ++i) {
if (rk[i] == 0) {
j = 0;
continue;
}
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j];)
++j;
h[rk[i] - 1] = j;
}
}
};
string s = "";
const int N = 2e6 + 7;
int fa[N];
int get(int x){
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
int pos[N], cnt[N];
struct Node{
int x, y;
ll lcp;
bool operator < (const Node o){
return lcp > o.lcp;
}
};
int main(){
int n = read();
cnt[0] = 0;
rep(i, 1, n){
string t;
cin >> t;
s = s + char(30 + i);
s = s + t;
cnt[i] = (int)s.size() - 1;
rep(j, cnt[i - 1] + 1, cnt[i] - 1) pos[j] = i;//表示时第几个串串
}
int m = (int)s.size() - 1;
rep(i, 0, m) fa[i] = i;
SA sa(s);
vector<Node> ans;
for(int i = 1; i < m; ++i){
if(pos[sa.sa[i]] == 0 || pos[sa.sa[i - 1]] == 0) continue;
ans.pb(Node{pos[sa.sa[i]], pos[sa.sa[i - 1]], sa.h[i]});
}
sort(ans.begin(), ans.end());
ll Ans = 0;
for(auto x:ans){
int fx = get(x.x);
int fy = get(x.y);
if(fx == fy) continue;
Ans += x.lcp;
fa[fx] = fy;
}
pprint(Ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7944kb
input:
4 icpc macau regional contest
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7648kb
input:
3 ababa babab aba
output:
7
result:
ok single line: '7'
Test #3:
score: -100
Runtime Error
input:
26 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...