oj.uz

Submission #887352

# Submission time Handle Problem Language Result Execution time Memory
887352 2023-12-14T09:55:39 Z serifefedartar Lampice (COCI19_lampice) C++17
56 / 110
 2057 ms 12636 KB 
#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(ans, ult_ans) << "\n";
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 7 ms 3420 KB Output is correct
3 Correct 30 ms 3676 KB Output is correct
4 Correct 24 ms 3676 KB Output is correct
5 Incorrect 1 ms 3420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 11612 KB Output is correct
2 Correct 822 ms 11864 KB Output is correct
3 Correct 609 ms 11864 KB Output is correct
4 Correct 688 ms 12248 KB Output is correct
5 Correct 996 ms 12636 KB Output is correct
6 Correct 321 ms 11600 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1651 ms 10368 KB Output is correct
2 Correct 2057 ms 10072 KB Output is correct
3 Correct 1806 ms 10068 KB Output is correct
4 Correct 1656 ms 9564 KB Output is correct
5 Correct 1456 ms 9564 KB Output is correct
6 Correct 1320 ms 9052 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 7 ms 3420 KB Output is correct
3 Correct 30 ms 3676 KB Output is correct
4 Correct 24 ms 3676 KB Output is correct
5 Incorrect 1 ms 3420 KB Output isn't correct
6 Halted 0 ms 0 KB -