Submission #600295

#	Time	Username	Problem	Language	Result	Execution time	Memory
600295		penguinhacker	Lampice (COCI19_lampice)	C++17	110 / 110	2025 ms	14204 KiB

lampice

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