oj.uz

Submission #600295

# Submission time Handle Problem Language Result Execution time Memory
600295 2022-07-20T16:56:16 Z penguinhacker Lampice (COCI19_lampice) C++17
110 / 110
 2025 ms 14204 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

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

ar<int, 2> operator+(ar<int, 2> a, ar<int, 2> b) {
	for (int i : {0, 1})
		if ((a[i]+=b[i])>=M)
			a[i]-=M;
	return a;
}

ar<int, 2> operator-(ar<int, 2> a, ar<int, 2> b) {
	for (int i : {0, 1})
		if ((a[i]-=b[i])<0)
			a[i]+=M;
	return a;
}

ar<int, 2> operator*(ar<int, 2> a, ar<int, 2> b) {
	for (int i : {0, 1})
		a[i]=(ll)a[i]*b[i]%M;
	return a;
}

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

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

Hash mk(char c) {
	ar<int, 2> id={c, c};
	return {id, id, 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][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][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]);
				ar<int, 2> cur=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][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, 1};
	for (int i=1; i<mxN; ++i)
		pp[i]=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 4180 KB Output is correct
2 Correct 9 ms 4324 KB Output is correct
3 Correct 26 ms 4448 KB Output is correct
4 Correct 19 ms 4436 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4240 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 12876 KB Output is correct
2 Correct 365 ms 13028 KB Output is correct
3 Correct 168 ms 13408 KB Output is correct
4 Correct 220 ms 13952 KB Output is correct
5 Correct 248 ms 14204 KB Output is correct
6 Correct 76 ms 12736 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 11848 KB Output is correct
2 Correct 630 ms 11500 KB Output is correct
3 Correct 601 ms 11768 KB Output is correct
4 Correct 313 ms 10692 KB Output is correct
5 Correct 507 ms 10756 KB Output is correct
6 Correct 467 ms 10316 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 9 ms 4324 KB Output is correct
3 Correct 26 ms 4448 KB Output is correct
4 Correct 19 ms 4436 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4240 KB Output is correct
8 Correct 489 ms 12876 KB Output is correct
9 Correct 365 ms 13028 KB Output is correct
10 Correct 168 ms 13408 KB Output is correct
11 Correct 220 ms 13952 KB Output is correct
12 Correct 248 ms 14204 KB Output is correct
13 Correct 76 ms 12736 KB Output is correct
14 Correct 652 ms 11848 KB Output is correct
15 Correct 630 ms 11500 KB Output is correct
16 Correct 601 ms 11768 KB Output is correct
17 Correct 313 ms 10692 KB Output is correct
18 Correct 507 ms 10756 KB Output is correct
19 Correct 467 ms 10316 KB Output is correct
20 Correct 1490 ms 8680 KB Output is correct
21 Correct 2025 ms 9788 KB Output is correct
22 Correct 1624 ms 10188 KB Output is correct
23 Correct 722 ms 7672 KB Output is correct
24 Correct 360 ms 9216 KB Output is correct
25 Correct 502 ms 8608 KB Output is correct
26 Correct 901 ms 11308 KB Output is correct
27 Correct 1624 ms 10612 KB Output is correct
28 Correct 545 ms 8100 KB Output is correct
29 Correct 610 ms 8268 KB Output is correct
30 Correct 298 ms 9872 KB Output is correct
31 Correct 602 ms 8672 KB Output is correct
32 Correct 396 ms 10940 KB Output is correct
33 Correct 1275 ms 10796 KB Output is correct