Submission #1012370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012370		biximo	Lampice (COCI19_lampice)	C++17	110 / 110	2735 ms	9812 KiB

lampice

#include <bits/stdc++.h>
#define N 50005
#define INF 1000000000
using namespace std;
typedef long long ll;
const ll B = 1307, MOD = (1LL<<61)-1;
struct Hash {
	ll hsf[N], hsb[N], mult[N];
	int len;
	void push_back(char c) {
		hsf[len+1] = ((__int128)hsf[len]*B+c)%MOD;
		hsb[len+1] = ((__int128)hsb[len]+(__int128)c*mult[len])%MOD;
		len ++;
	}
	void pop_back() {
		len --;
	}
	void clear() {
		len = 0;
	}
	bool isPalindrome(int ln) {
		return hsf[ln] == hsb[ln];
	}
	long long query(int ln) {
		return (hsf[len]-(__int128)hsf[len-ln]*mult[ln]%MOD+MOD)%MOD;
	}
	Hash() {
		mult[0] = 1;
		for(int i = 1; i < N; i ++) {
			mult[i] = (__int128)mult[i-1]*B%MOD;
		}
		len = 0;
	}
} hs;


bool vs[N];
vector<int> adj[N];
int tree_sz[N];
void DFS_sz(int c, int p) {
	tree_sz[c] = 1;
	for(int i: adj[c]) {
		if(i == p || vs[i]) continue;
		DFS_sz(i, c);
		tree_sz[c] += tree_sz[i];
	}
}
int DFS_cent(int c, int p, int tsz) {
	for(int i: adj[c]) {
		if(i == p || vs[i] || tree_sz[i]*2 < tsz) continue;
		return DFS_cent(i, c, tsz);
	}
	return c;
}

string S;

set<ll> st;

bool DFS_update(int c, int p, int dpt, int len) {
	hs.push_back(S[c]);
	if(dpt*2 >= len && hs.isPalindrome(2*dpt-len)) {
		st.insert(hs.query(len-dpt));
	}
	if(dpt == len && hs.isPalindrome(len)) return 1;
	for(int i: adj[c]) {
		if(i == p || vs[i]) continue;
		if(DFS_update(i, c, dpt+1, len)) return 1;
	}
	hs.pop_back();
	return 0;
}

bool DFS_search(int c, int p, int dpt, int len) {
	hs.push_back(S[c]);
	if(dpt*2 <= len && st.count(hs.query(dpt))) {
		return 1;
	}
	if(dpt == len && hs.isPalindrome(len)) return 1;
	for(int i: adj[c]) {
		if(i == p || vs[i]) continue;
		if(DFS_search(i, c, dpt+1, len)) return 1;
	}
	hs.pop_back();
	return 0;
}

bool works(int c, int len) {

	DFS_sz(c,-1);
	int cent = DFS_cent(c, -1, tree_sz[c]);
	vs[cent] = 1;
	for(int z = 0; z < 2; z ++) {
		st.clear();
		for(int i: adj[cent]) {
			if(vs[i]) continue;
			hs.clear();
			if(DFS_search(i, cent, 1, len)) return 1;
			hs.clear();
			hs.push_back(S[cent]);
			if(DFS_update(i, cent, 2, len)) return 1;
		}

		reverse(adj[cent].begin(),adj[cent].end());
	}

	for(int i: adj[cent]) {
		if(vs[i]) continue;
		if(works(i, len)) return 1;
	}

	return 0;

}
int n;

bool works(int len) {

	for(int i = 1; i <= n; i ++) vs[i] = 0;

	return works(1, len);

}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> S;
    S.insert(S.begin(), ' ');
    for(int i = 1, u, v; i < n; i ++) {
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    int l=1,h=n/2,ans=1;
    while(l <= h) {
    	int md = (l+h)>>1;
    	if(works(md*2)) {
    		ans = max(ans, md*2);
    		l = md+1;
    	} else {
    		h = md-1;
    	}
    }
    l=1,h=n/2;
    while(l <= h) {
    	int md = (l+h)>>1;
    	if(works(md*2+1)) {
    		ans = max(ans, md*2+1);
    		l = md+1;
    	} else {
    		h = md-1;
    	}
    }
    cout << ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37