oj.uz

Submission #887360

# Submission time Handle Problem Language Result Execution time Memory
887360 2023-12-14T09:59:44 Z serifefedartar Lampice (COCI19_lampice) C++17
110 / 110
 2152 ms 11352 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#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 24 ms 3760 KB Output is correct
4 Correct 36 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 737 ms 10188 KB Output is correct
2 Correct 809 ms 10584 KB Output is correct
3 Correct 584 ms 10584 KB Output is correct
4 Correct 743 ms 11088 KB Output is correct
5 Correct 1078 ms 11352 KB Output is correct
6 Correct 332 ms 10072 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1654 ms 9808 KB Output is correct
2 Correct 2023 ms 9336 KB Output is correct
3 Correct 1917 ms 9564 KB Output is correct
4 Correct 1690 ms 8796 KB Output is correct
5 Correct 1574 ms 8784 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 24 ms 3760 KB Output is correct
4 Correct 36 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 737 ms 10188 KB Output is correct
9 Correct 809 ms 10584 KB Output is correct
10 Correct 584 ms 10584 KB Output is correct
11 Correct 743 ms 11088 KB Output is correct
12 Correct 1078 ms 11352 KB Output is correct
13 Correct 332 ms 10072 KB Output is correct
14 Correct 1654 ms 9808 KB Output is correct
15 Correct 2023 ms 9336 KB Output is correct
16 Correct 1917 ms 9564 KB Output is correct
17 Correct 1690 ms 8796 KB Output is correct
18 Correct 1574 ms 8784 KB Output is correct
19 Correct 1335 ms 8536 KB Output is correct
20 Correct 1285 ms 7260 KB Output is correct
21 Correct 1588 ms 8028 KB Output is correct
22 Correct 2017 ms 8536 KB Output is correct
23 Correct 483 ms 6748 KB Output is correct
24 Correct 1583 ms 7772 KB Output is correct
25 Correct 1479 ms 7260 KB Output is correct
26 Correct 1899 ms 9296 KB Output is correct
27 Correct 2152 ms 8788 KB Output is correct
28 Correct 1264 ms 6808 KB Output is correct
29 Correct 1274 ms 6744 KB Output is correct
30 Correct 1531 ms 8272 KB Output is correct
31 Correct 1316 ms 7256 KB Output is correct
32 Correct 1330 ms 9028 KB Output is correct
33 Correct 1178 ms 8788 KB Output is correct