結果
問題 | No.962 LCPs |
ユーザー |
|
提出日時 | 2019-12-25 07:06:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,255 bytes |
コンパイル時間 | 1,826 ms |
コンパイル使用メモリ | 175,992 KB |
実行使用メモリ | 15,772 KB |
最終ジャッジ日時 | 2024-09-24 08:16:48 |
合計ジャッジ時間 | 4,956 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 64 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct unionfind { vector<int> dat; unionfind(int n) : dat(n, -1) {} int find(int x) { if (dat[x] < 0) return x; return dat[x] = find(dat[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (dat[x] > dat[y]) swap(x, y); dat[x] += dat[y]; dat[y] = x; } int size(int x) { return -dat[find(x)]; } }; int lcp(string s, string t) { int k = 0; while (k < s.size() and k < t.size() and s[k] == t[k]) k++; return k; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<string> S(N); for (int i = 0; i < N; i++) { cin >> S[i]; } vector<vector<int>> pos(200001); for (int i = 0; i + 1 < N; i++) { pos[lcp(S[i], S[i + 1])].push_back(i); } ll ans = 0; ll ima = 0; unionfind uf(N); auto f = [&](ll n) { return n * (n + 1) * (n + 2) / 6; }; for (int i = 200000; i >= 1; i--) { for (int j : pos[i]) { ima -= f(uf.size(j)); ima -= f(uf.size(j + 1)); uf.unite(j, j + 1); ima += f(uf.size(j)); } ans += ima; } for (int i = 0; i < N; i++) { ans += S[i].size(); } cout << ans << endl; }