oj.uz

Submission #600298

# Submission time Handle Problem Language Result Execution time Memory
600298 2022-07-20T17:04:02 Z penguinhacker Lampice (COCI19_lampice) C++17
110 / 110
 1654 ms 11824 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e4, P=129, M=1e9+696969;
int n, sz[mxN], ts, ans=1, pp[mxN];
string s;
vector<int> adj[mxN];
bool dead[mxN];
map<int, int> mp[mxN+1];

int add(int a, int b) {
	if ((a+=b)>=M)
		a-=M;
	return a;
}

int sub(int a, int b) {
	if ((a-=b)<0)
		a+=M;
	return a;
}

int mul(int a, int b) {
	return (ll)a*b%M;
}

struct Hash {
	int a=0, b=0, length=0;
};
vector<vector<Hash>> cmps;

Hash operator+(Hash a, Hash b) {
	return {add(mul(a.a, pp[b.length]), b.a), add(mul(b.b, pp[a.length]), a.b), a.length+b.length};
}

Hash mk(char c) {
	return {c, c, 1};
}

int dfs1(int u, int p=-1) {
	sz[u]=1;
	for (int v : adj[u])
		if (!dead[v]&&v!=p)
			sz[u]+=dfs1(v, u);
	return sz[u];
}

int dfs2(int u, int p=-1) {
	for (int v : adj[u])
		if (!dead[v]&&v!=p&&sz[v]>ts/2)
			return dfs2(v, u);
	return u;
}

void dfs3(int u, int p=-1, Hash h=Hash()) {
	h=h+mk(s[u]);
	cmps.back().push_back(h);
	for (int v : adj[u])
		if (!dead[v]&&v!=p)
			dfs3(v, u, h);
}

bool ok(int rt, int x) {
	for (int rep=0; rep<2; ++rep, ++x) {
		for (vector<Hash>& v : cmps)
			for (Hash& h : v)
				if (h.length+2<=x)
					++mp[h.length][sub(mul(h.b, pp[x-h.length]), h.a)];
		for (vector<Hash>& v : cmps) {
			for (Hash& h : v)
				if (h.length+2<=x)
					--mp[h.length][sub(mul(h.b, pp[x-h.length]), h.a)];
			for (Hash h : v) {
				if (h.length+1>=x)
					continue;
				swap(h.a, h.b);
				h=h+mk(s[rt]);
				int cur=sub(mul(h.a, pp[x-h.length]), h.b);
				auto it=mp[x-h.length].find(cur);
				if (it!=mp[x-h.length].end()&&it->second) {
					for (int i=1; i+2<=x; ++i)
						mp[i].clear();
					return 1;
				}
			}
			for (Hash& h : v)
				if (h.length+2<=x)
					++mp[h.length][sub(mul(h.b, pp[x-h.length]), h.a)];
		}
		for (int i=1; i+2<=x; ++i)
			mp[i].clear();
	}
	return 0;
}

void dfs4(int u=0) {
	ts=dfs1(u);
	u=dfs2(u);
	cmps.clear();
	for (int v : adj[u])
		if (!dead[v]) {
			cmps.push_back({});
			dfs3(v, u);
		}
	for (vector<Hash>& v : cmps)
		for (Hash& h : v) {
			Hash x=mk(s[u])+h;
			if (x.a==x.b)
				ans=max(ans, x.length);
		}
	if (ans>=ts)
		return;
	int lb=ans, rb=ts;
	while(lb<rb) {
		int mid=(lb+rb+1)/2;
		if (ok(u, mid))
			lb=mid;
		else
			rb=mid-1;
	}
	ans=max(ans, lb);
	dead[u]=1;
	for (int v : adj[u])
		if (!dead[v])
			dfs4(v);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	pp[0]=1;
	for (int i=1; i<mxN; ++i)
		pp[i]=mul(pp[i-1], P);
	cin >> n >> s;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs4();
	cout << ans;
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4052 KB Output is correct
2 Correct 8 ms 4052 KB Output is correct
3 Correct 20 ms 4192 KB Output is correct
4 Correct 14 ms 4192 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 2 ms 3924 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 10832 KB Output is correct
2 Correct 273 ms 11008 KB Output is correct
3 Correct 127 ms 11216 KB Output is correct
4 Correct 157 ms 11576 KB Output is correct
5 Correct 184 ms 11824 KB Output is correct
6 Correct 56 ms 10824 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 9568 KB Output is correct
2 Correct 456 ms 9308 KB Output is correct
3 Correct 430 ms 9412 KB Output is correct
4 Correct 233 ms 8504 KB Output is correct
5 Correct 413 ms 8864 KB Output is correct
6 Correct 339 ms 8404 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4052 KB Output is correct
2 Correct 8 ms 4052 KB Output is correct
3 Correct 20 ms 4192 KB Output is correct
4 Correct 14 ms 4192 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 2 ms 3924 KB Output is correct
8 Correct 340 ms 10832 KB Output is correct
9 Correct 273 ms 11008 KB Output is correct
10 Correct 127 ms 11216 KB Output is correct
11 Correct 157 ms 11576 KB Output is correct
12 Correct 184 ms 11824 KB Output is correct
13 Correct 56 ms 10824 KB Output is correct
14 Correct 484 ms 9568 KB Output is correct
15 Correct 456 ms 9308 KB Output is correct
16 Correct 430 ms 9412 KB Output is correct
17 Correct 233 ms 8504 KB Output is correct
18 Correct 413 ms 8864 KB Output is correct
19 Correct 339 ms 8404 KB Output is correct
20 Correct 1206 ms 7244 KB Output is correct
21 Correct 1654 ms 8156 KB Output is correct
22 Correct 1321 ms 8280 KB Output is correct
23 Correct 655 ms 6556 KB Output is correct
24 Correct 258 ms 7632 KB Output is correct
25 Correct 357 ms 7276 KB Output is correct
26 Correct 672 ms 9032 KB Output is correct
27 Correct 1275 ms 8656 KB Output is correct
28 Correct 346 ms 6740 KB Output is correct
29 Correct 363 ms 6740 KB Output is correct
30 Correct 195 ms 8144 KB Output is correct
31 Correct 390 ms 7104 KB Output is correct
32 Correct 336 ms 9224 KB Output is correct
33 Correct 1098 ms 8736 KB Output is correct