oj.uz

Submission #1012355

# Submission time Handle Problem Language Result Execution time Memory
1012355 2024-07-02T03:43:13 Z biximo Lampice (COCI19_lampice) C++17
0 / 110
 2395 ms 9136 KB 
#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]+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;

void DFS_update(int c, int p, int dpt, int len) {
	hs.push_back(S[c]);
	// cout << c << " " <<dpt << " " << len << " " << hs.query(dpt) << "\n";
	if(dpt*2 >= len && hs.isPalindrome(2*dpt-len)) {
		st.insert(hs.query(len-dpt));
	}
	for(int i: adj[c]) {
		if(i == p || vs[i]) continue;
		DFS_update(i, c, dpt+1, len);
	}
	hs.pop_back();
}

bool DFS_search(int c, int p, int dpt, int len) {
	hs.push_back(S[c]);
	// cout << c << " " << dpt << " " << len << " " << hs.query(dpt) << "\n";
	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;
	// cout << cent << "\n";
	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]);
			DFS_update(i, cent, 2, len);
		}

		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;
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;
    	for(int i = 1; i <= n; i ++) vs[i] = 0;
    	if(works(1,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;
    	for(int i = 1; i <= n; i ++) vs[i] = 0;
    		// cout << "Queried! " << md*2+1 << "\n";
    	if(works(1,md*2+1)) {
    		ans = max(ans, md*2+1);
    		l = md+1;
    	} else {
    		h = md-1;
    	}
    }
    cout << ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Incorrect 5 ms 2908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1353 ms 9136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2395 ms 7432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Incorrect 5 ms 2908 KB Output isn't correct
3 Halted 0 ms 0 KB -