Submission #887353

#	Time	Username	Problem	Language	Result	Execution time	Memory
887353		serifefedartar	Lampice (COCI19_lampice)	C++17	110 / 110	2288 ms	12124 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 21
#define MAXN 50005

const ll P = 31;
vector<vector<int>> graph;
string s;
ll marked[MAXN], sz[MAXN], powP[MAXN];
bool ch = false;
int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u == parent || marked[u])
			continue;
		sz[node] += get_sz(u, node);
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u != parent && !marked[u] && sz[u] * 2 >= n)
			return find_centro(u, node, n);
	}
	return node;
}

int ref_val;
set<ll> hashes[MAXN];
void eval(int node, int parent, ll normal_hash, ll rev_hash, ll dist) {
	if (ch || dist > ref_val)
		return ;
	normal_hash = (normal_hash * P + (s[node] - 'a' + 1)) % MOD;
	rev_hash = (rev_hash + powP[dist - 1] * (s[node] - 'a' + 1)) % MOD;
	if (rev_hash == normal_hash && dist == ref_val) {
		ch = true;
		return ;
	}
	if (ref_val == dist)
		return ;

	ll hash_req = (rev_hash * powP[ref_val - dist] - normal_hash + MOD) % MOD;
	if (hashes[ref_val - dist].count(hash_req))
		ch = true;

	for (auto u : graph[node]) {
		if (u == parent || marked[u])
			continue;
		eval(u, node, normal_hash, rev_hash, dist + 1);
	}
}

void add(int node, int parent, ll normal_hash, ll rev_hash, ll dist) {
	if (ch || dist > ref_val)
		return ;
	normal_hash = (normal_hash * P + (s[node] - 'a' + 1)) % MOD;
	rev_hash = (rev_hash + powP[dist - 1] * (s[node] - 'a' + 1)) % MOD;
	if (rev_hash == normal_hash && dist == ref_val) {
		ch = true;
		return ;
	}
	if (ref_val == dist)
		return ;

	ll hash_this = (rev_hash * powP[ref_val - dist] - normal_hash + MOD) % MOD;
	hashes[dist].insert(hash_this);

	for (auto u : graph[node]) {
		if (u == parent || marked[u])
			continue;
		add(u, node, normal_hash, rev_hash, dist + 1);
	}
}

void decompose(int node) {
	int n = get_sz(node, node);
	int centro = find_centro(node, node, n);
	marked[centro] = true;

	for (int i = 0; i <= sz[node]; i++)
		hashes[i].clear();
	for (auto u : graph[centro]) {
		if (!marked[u]) {
			eval(u, centro, s[centro] - 'a' + 1, s[centro] - 'a' + 1, 2);
			add(u, centro, 0, 0, 1);
		}
	}

	for (auto u : graph[centro]) {
		if (!marked[u])
			decompose(u);
	}
}

bool check(int mid) {
	ch = 0, ref_val = mid;
	for (int i = 0; i < MAXN; i++)
		marked[i] = false;
	decompose(1);
	return ch;
}

int main() {
	fast
	powP[0] = 1;
	for (int i = 1; i < MAXN; i++)
		powP[i] = (powP[i-1] * P) % MOD;
	int N, a, b;
	cin >> N >> s;
	s = "#" + s;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i < N; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	int L = 0;
	int R = (N - 1) / 2;
	int ans = -1;
	while (R >= L) {
		int mid = L + (R - L) / 2;
		if (check(2 * mid + 1)) {
			ans = 2 * mid + 1;
			L = mid + 1;
		} else
			R = mid - 1;
	}

	int ult_ans = ans;
	L = 1;
	R = N / 2;
	ans = -1;
	while (R >= L) {
		int mid = L + (R - L) / 2;
		if (check(2 * mid)) {
			ans = 2 * mid;
			L = mid + 1;
		} else
			R = mid - 1;
	}

	cout << max(1, max(ans, ult_ans)) << "\n";
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37