oj.uz

Submission #887356

# Submission time Handle Problem Language Result Execution time Memory
887356 2023-12-14T09:58:22 Z serifefedartar Lampice (COCI19_lampice) C++17
110 / 110
 2194 ms 11356 KB 
#pragma GCC optimize("O3,unroll-loops")
#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.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 23 ms 3636 KB Output is correct
4 Correct 26 ms 3676 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 10332 KB Output is correct
2 Correct 786 ms 10588 KB Output is correct
3 Correct 564 ms 10584 KB Output is correct
4 Correct 714 ms 11100 KB Output is correct
5 Correct 1027 ms 11356 KB Output is correct
6 Correct 310 ms 10068 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1611 ms 9820 KB Output is correct
2 Correct 2031 ms 9436 KB Output is correct
3 Correct 1803 ms 9648 KB Output is correct
4 Correct 1680 ms 8796 KB Output is correct
5 Correct 1421 ms 8796 KB Output is correct
6 Correct 1335 ms 8536 KB Output is correct

Subtask #4
37.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 23 ms 3636 KB Output is correct
4 Correct 26 ms 3676 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 735 ms 10332 KB Output is correct
9 Correct 786 ms 10588 KB Output is correct
10 Correct 564 ms 10584 KB Output is correct
11 Correct 714 ms 11100 KB Output is correct
12 Correct 1027 ms 11356 KB Output is correct
13 Correct 310 ms 10068 KB Output is correct
14 Correct 1611 ms 9820 KB Output is correct
15 Correct 2031 ms 9436 KB Output is correct
16 Correct 1803 ms 9648 KB Output is correct
17 Correct 1680 ms 8796 KB Output is correct
18 Correct 1421 ms 8796 KB Output is correct
19 Correct 1335 ms 8536 KB Output is correct
20 Correct 1273 ms 7256 KB Output is correct
21 Correct 1549 ms 8344 KB Output is correct
22 Correct 1990 ms 8524 KB Output is correct
23 Correct 478 ms 6608 KB Output is correct
24 Correct 1568 ms 7772 KB Output is correct
25 Correct 1448 ms 7256 KB Output is correct
26 Correct 1936 ms 9292 KB Output is correct
27 Correct 2194 ms 8796 KB Output is correct
28 Correct 1272 ms 6780 KB Output is correct
29 Correct 1255 ms 6748 KB Output is correct
30 Correct 1500 ms 8280 KB Output is correct
31 Correct 1298 ms 7260 KB Output is correct
32 Correct 1255 ms 9048 KB Output is correct
33 Correct 1114 ms 8796 KB Output is correct