結果

問題 No.2606 Mirror Relay
ユーザー Rubikun
提出日時 2024-01-12 22:39:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 70 ms / 2,000 ms
コード長 5,592 bytes
コンパイル時間 2,306 ms
コンパイル使用メモリ 209,100 KB
最終ジャッジ日時 2025-02-18 18:44:27
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// https://math314.hateblo.jp/entry/2016/12/19/005919
#include <bits/stdc++.h>
using namespace std;
struct PalindromicTree {
//
// private:
struct node {
map<char, int> link;
int suffix_link;
int len;
int count;
};
vector<node> c;
string s;
int active_idx;
node* create_node() {
c.emplace_back();
node* ret = &c.back();
ret->count = 0;
return ret;
}
// this->s
int find_prev_palindrome_idx(int node_id) {
const int pos = int(s.size()) - 1;
while (true) {
const int opposite_side_idx = pos - 1 - c[node_id].len;
if (opposite_side_idx >= 0 && s[opposite_side_idx] == s.back()) break;
node_id = c[node_id].suffix_link; //
}
return node_id;
}
bool debug_id2string_dfs(int v, int id, vector<char>& charas) {
if (v == id) return true;
for (auto kv : c[v].link) {
if (debug_id2string_dfs(kv.second, id, charas)) {
charas.push_back(kv.first);
return true;
}
}
return false;
}
public:
PalindromicTree() {
node* size_m1 = create_node(); // -1
size_m1->suffix_link = 0; // -1 suffix
size_m1->len = -1;
node* size_0 = create_node(); // 0
size_0->suffix_link = 0; // -1
size_0->len = 0;
active_idx = 0;
}
int get_active_idx() const {
return active_idx;
}
node* get_node(int id) {
return &c[id];
}
void add(char ch) {
s.push_back(ch);
// ch + [A] + ch
const int a = find_prev_palindrome_idx(active_idx);
//
const auto inserted_result = c[a].link.insert(make_pair(ch, int(c.size())));
active_idx = inserted_result.first->second; // insertiteratorindex
if (!inserted_result.second) {
c[active_idx].count++; //
return; //
}
//
node* nnode = create_node();
nnode->count = 1;
nnode->len = c[a].len + 2; // ch + [A] + ch len(A) + 2
// suffix_link
if (nnode->len == 1) {
// suffix_linksize 0
nnode->suffix_link = 1;
} else {
// ch + [B] + ch a
const int b = find_prev_palindrome_idx(c[a].suffix_link);
nnode->suffix_link = c[b].link[ch];
}
}
//
// O(n)
vector<int> build_frequency() {
vector<int> frequency(c.size());
//id < idid
for (int i = int(c.size()) - 1; i > 0; i--) {
frequency[i] += c[i].count;
frequency[c[i].suffix_link] += frequency[i];
}
return frequency;
}
// debug
// id
// O(n)
string debug_id2string(int id) {
if (id == 0) {
return "(-1)";
} else if (id == 1) {
return "(0)";
}
vector<char> charas;
debug_id2string_dfs(0, id, charas);
debug_id2string_dfs(1, id, charas);
string ret(charas.begin(),charas.end());
int start = int(charas.size()) - 1;
if (c[id].len % 2 == 1) start--;
for (int i = start; i >= 0; i--) ret.push_back(charas[i]);
return ret;
}
void display_frequencies() {
auto freq = build_frequency();
printf("frequencies of each palindrome...\n");
for (int i = 0; i < int(c.size()); i++) {
const string palindrome = debug_id2string(i);
printf(" %s : %d\n", palindrome.c_str(), freq[i]);
}
}
};
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
vector<int> G[MAX];
ll ad[MAX],dp[MAX];
int main() {
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
string S;cin>>S;
PalindromicTree pt;
for (auto c : S) {
pt.add(c); // 1
//pt.display_frequencies();
}
auto fre=pt.build_frequency();
for(int i=2;i<si(fre);i++){
auto x=pt.get_node(i);
//cout<<x->suffix_link<<" "<<x->len<<" "<<x->count<<endl;
ad[i]+=(ll)(fre[i])*(x->len);
G[x->suffix_link].push_back(i);
}
ll ans=0;
for(int i=0;i<si(fre);i++){
dp[i]+=ad[i];
chmax(ans,dp[i]);
for(int to:G[i]) chmax(dp[to],dp[i]);
}
cout<<ans<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0