oj.uz

Submission #1012370

# Submission time Handle Problem Language Result Execution time Memory
1012370 2024-07-02T04:34:33 Z biximo Lampice (COCI19_lampice) C++17
110 / 110
 2735 ms 9812 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]+(__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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 5 ms 1884 KB Output is correct
3 Correct 20 ms 2140 KB Output is correct
4 Correct 24 ms 2140 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1828 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1307 ms 8900 KB Output is correct
2 Correct 756 ms 8548 KB Output is correct
3 Correct 533 ms 8528 KB Output is correct
4 Correct 698 ms 9056 KB Output is correct
5 Correct 1091 ms 9812 KB Output is correct
6 Correct 150 ms 9308 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2735 ms 6612 KB Output is correct
2 Correct 2329 ms 6096 KB Output is correct
3 Correct 2188 ms 6460 KB Output is correct
4 Correct 2410 ms 6240 KB Output is correct
5 Correct 1462 ms 5948 KB Output is correct
6 Correct 1719 ms 5716 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 5 ms 1884 KB Output is correct
3 Correct 20 ms 2140 KB Output is correct
4 Correct 24 ms 2140 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1828 KB Output is correct
8 Correct 1307 ms 8900 KB Output is correct
9 Correct 756 ms 8548 KB Output is correct
10 Correct 533 ms 8528 KB Output is correct
11 Correct 698 ms 9056 KB Output is correct
12 Correct 1091 ms 9812 KB Output is correct
13 Correct 150 ms 9308 KB Output is correct
14 Correct 2735 ms 6612 KB Output is correct
15 Correct 2329 ms 6096 KB Output is correct
16 Correct 2188 ms 6460 KB Output is correct
17 Correct 2410 ms 6240 KB Output is correct
18 Correct 1462 ms 5948 KB Output is correct
19 Correct 1719 ms 5716 KB Output is correct
20 Correct 1094 ms 4316 KB Output is correct
21 Correct 1098 ms 4436 KB Output is correct
22 Correct 1726 ms 5092 KB Output is correct
23 Correct 620 ms 4780 KB Output is correct
24 Correct 1791 ms 5316 KB Output is correct
25 Correct 1721 ms 5116 KB Output is correct
26 Correct 1955 ms 6332 KB Output is correct
27 Correct 2207 ms 5460 KB Output is correct
28 Correct 1588 ms 4608 KB Output is correct
29 Correct 1609 ms 4656 KB Output is correct
30 Correct 1717 ms 5968 KB Output is correct
31 Correct 1698 ms 4952 KB Output is correct
32 Correct 1027 ms 7080 KB Output is correct
33 Correct 697 ms 5716 KB Output is correct