Submission #600298

#	Time	Username	Problem	Language	Result	Execution time	Memory
600298		penguinhacker	Lampice (COCI19_lampice)	C++17	110 / 110	1654 ms	11824 KiB

lampice

#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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37