#943790 (C++23) No.2606 Mirror Relay

提出ソース

結果

問題	No.2606 Mirror Relay
ユーザー	Aeren
提出日時	2024-01-12 23:35:16
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	57 ms / 2,000 ms
コード長	3,196 bytes
コンパイル時間	4,201 ms
コンパイル使用メモリ	268,376 KB
実行使用メモリ	52,800 KB
最終ジャッジ日時	2024-01-12 23:35:24
合計ジャッジ時間	6,260 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	3 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	3 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	2 ms 6,676 KB
testcase_13	AC	2 ms 6,676 KB
testcase_14	AC	2 ms 6,676 KB
testcase_15	AC	2 ms 6,676 KB
testcase_16	AC	2 ms 6,676 KB
testcase_17	AC	2 ms 6,676 KB
testcase_18	AC	2 ms 6,676 KB
testcase_19	AC	2 ms 6,676 KB
testcase_20	AC	2 ms 6,676 KB
testcase_21	AC	3 ms 6,676 KB
testcase_22	AC	2 ms 6,676 KB
testcase_23	AC	2 ms 6,676 KB
testcase_24	AC	3 ms 6,676 KB
testcase_25	AC	3 ms 6,676 KB
testcase_26	AC	3 ms 6,676 KB
testcase_27	AC	3 ms 6,676 KB
testcase_28	AC	3 ms 6,676 KB
testcase_29	AC	2 ms 6,676 KB
testcase_30	AC	2 ms 6,676 KB
testcase_31	AC	3 ms 6,676 KB
testcase_32	AC	3 ms 6,676 KB
testcase_33	AC	2 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB
testcase_35	AC	2 ms 6,676 KB
testcase_36	AC	2 ms 6,676 KB
testcase_37	AC	2 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	9 ms 7,276 KB
testcase_40	AC	8 ms 7,020 KB
testcase_41	AC	9 ms 6,764 KB
testcase_42	AC	9 ms 7,276 KB
testcase_43	AC	8 ms 6,764 KB
testcase_44	AC	9 ms 7,276 KB
testcase_45	AC	9 ms 7,020 KB
testcase_46	AC	9 ms 6,764 KB
testcase_47	AC	9 ms 7,276 KB
testcase_48	AC	8 ms 7,020 KB
testcase_49	AC	22 ms 17,860 KB
testcase_50	AC	22 ms 18,448 KB
testcase_51	AC	23 ms 18,320 KB
testcase_52	AC	22 ms 17,720 KB
testcase_53	AC	29 ms 19,632 KB
testcase_54	AC	23 ms 18,472 KB
testcase_55	AC	28 ms 24,428 KB
testcase_56	AC	22 ms 17,556 KB
testcase_57	AC	22 ms 17,820 KB
testcase_58	AC	26 ms 22,256 KB
testcase_59	AC	10 ms 7,276 KB
testcase_60	AC	9 ms 7,276 KB
testcase_61	AC	9 ms 6,764 KB
testcase_62	AC	9 ms 7,020 KB
testcase_63	AC	9 ms 6,892 KB
testcase_64	AC	9 ms 7,020 KB
testcase_65	AC	9 ms 7,148 KB
testcase_66	AC	8 ms 7,020 KB
testcase_67	AC	9 ms 7,020 KB
testcase_68	AC	8 ms 7,020 KB
testcase_69	AC	57 ms 52,800 KB
testcase_70	AC	2 ms 6,676 KB
testcase_71	AC	2 ms 6,676 KB
testcase_72	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<class F>
struct y_combinator_result{
	F f;
	template<class T> explicit y_combinator_result(T &&f): f(forward<T>(f)){ }
	template<class ...Args> decltype(auto) operator()(Args &&...args){ return f(ref(*this), forward<Args>(args)...); }
};
template<class F>
decltype(auto) y_combinator(F &&f){
	return y_combinator_result<decay_t<F>>(forward<F>(f));
}

// Each node represents a unique palindromic substring plus 0 and 1 node representing empty even and odd string
// Adjacency_Type: array<int, X> or map<Char_Type, int> where X is the size of the alphabet
template<class Char_Type, class Adjacency_Type>
struct palindrome_automaton{
	// Begin States
	// len: length of the palindrome
	// link: suffix link
	// serial_link[u]: longest proper suffix v with len[u] - len[link[u]] != len[v] - len[link[v]]
	// depth: # of suffix links till root
	// occurence: # of occurences of the palindrome as a longest proper palindromic suffix of a prefix
	vector<int> len{0, -1}, link{1, 0}, serial_link{0, 0}, depth{0, 0}, occurence{1, 0};
	vector<Adjacency_Type> next = vector<Adjacency_Type>(2);
	// End States
	vector<Char_Type> s{-1};
	vector<int> last{0};
	long long palindromic_substring_count = 0;
	int new_state(int l, int u){
		len.push_back(l);
		link.push_back(u);
		serial_link.push_back(l - len[u] == len[u] - len[link[u]] ? serial_link[u] : u);
		depth.push_back(depth[u] + 1);
		next.emplace_back();
		occurence.push_back(0);
		return (int)len.size() - 1;
	}
	void extend(const vector<Char_Type> &s){
		for(auto c: s) extend(c);
	}
	void extend(Char_Type c){
		s.push_back(c);
		int l = last.back();
		while(s[(int)s.size() - len[l] - 2] != s.back()) l = link[l];
		if(!next[l][c]){
			int u = link[l];
			while(s[(int)s.size() - len[u] - 2] != s.back()) u = link[u];
			int v = new_state(len[l] + 2, next[u][c]);
			next[l][c] = v; // Separated for UB in C++14 or below
		}
		last.push_back(next[l][c]);
		palindromic_substring_count += depth[last.back()];
		++ occurence[last.back()];
	}
	int size() const{ // # of states
		return (int)len.size();
	}
	// count: # of occurences of the palindrome
	vector<int> count;
	vector<vector<int>> inv_link;
	void init_count(){
		count = occurence, inv_link.assign(size(), {});
		for(auto u = 2; u < (int)size(); ++ u) inv_link[link[u]].push_back(u);
		auto dfs = [&](auto self, int u)->void{
			for(auto v: inv_link[u]) self(self, v), count[u] += count[v];
		};
		dfs(dfs, 0);
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	vector<int> s;
	{
		string t;
		cin >> t;
		for(auto c: t){
			s.push_back(c - 'a');
		}
	}
	const int mx = 26;
	palindrome_automaton<int, array<int, mx>> aut;
	aut.extend(s);
	aut.init_count();
	vector<long long> res(aut.size());
	for(auto s = 0; s < 2; ++ s){
		y_combinator([&](auto self, int u)->void{
			res[u] += 1LL * aut.count[u] * max(0, aut.len[u]);
			for(auto v: aut.inv_link[u]){
				if(v <= 1){
					continue;
				}
				res[v] += res[u];
				self(v);
			}
		})(s);
	}
	cout << ranges::max(res) << "\n";
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード