oj.uz

Submission #637445

# Submission time Handle Problem Language Result Execution time Memory
637445 2022-09-01T19:23:07 Z vovamr Lampice (COCI19_lampice) C++17
110 / 110
 4750 ms 10276 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

constexpr int md = 1e9 + 9; constexpr int iv2 = (md + 1) / 2;
inline int add(int a, int b) { a += b; if(a>=md){a-=md;} return a; }
inline int sub(int a, int b) { a -= b; if(a<0){a+=md;} return a; }
inline int mul(int a, int b) { return (ll)a * b % md; }
inline int bp(int a, int n) { int res = 1;
	for (; n; n >>= 1, a = mul(a, a)) {
		if (n & 1) res = mul(res, a);
	} return res;
}
inline int inv(int a) { return bp(a, md - 2); }
constexpr int p = 10039;

const int N = 5e4 + 100;

int pw[N];
inline void calc() {
	pw[0] = 1;
	for (int i = 1; i < N; ++i) pw[i] = mul(pw[i - 1], p);
}

int a[N];

ve<int> gr[N];
int used[N], sz[N];
inline void dfs1(int v, int p) {
	sz[v] = 1;
	for (auto &to : gr[v]) if (to != p && !used[to]) {
		dfs1(to, v);
		sz[v] += sz[to];
	}
}
inline int centr(int v, int p, int n) {
	for (auto &to : gr[v]) if (to != p && !used[to] && sz[to] > n / 2) {
		return centr(to, v, n);
	} return v;
}

int u[N], d[N];
inline void hashes(int v, int p, int h) {
	if (v == p) u[v] = d[v] = a[v];
	for (auto &to : gr[v]) if (to != p && !used[to]) {
		u[to] = add(u[v], mul(pw[h + 1], a[to]));
		d[to] = add(a[to], mul(pw[1], d[v]));
		hashes(to, v, h + 1);
	}
}

gp_hash_table<int,int> mp;

int cur_path[N];
int S = 0;

inline bool dfs(int v, int p, const int &l) {

	cur_path[S++] = v;
	if (S == l && u[v] == d[v]) return 1;

	int x = l + 1 - S; // other length
	int id = S - x;

	if (id >= 0 && id < S && S >= x) {
		int node = cur_path[id];
		if (u[node] == d[node]) {
			int P = !id ? 0 : d[cur_path[id - 1]];
			int H = sub(d[v], mul( P, pw[x] ));
			if (mp.find(H) != mp.end()) return 1;
		}
	}

	for (auto &to : gr[v]) {
		if (to == p || used[to]) continue;
		if (dfs(to, v, l)) return 1;
	} --S; return 0;
}

inline void add(int v, int p, const int &delta) {
	if (!(mp[d[v]] += delta)) mp.erase(d[v]);
	for (auto &to : gr[v]) if (to != p && !used[to]) {
		add(to, v, delta);
	}
}

inline bool cd(int v, int p, const int &l) {
	used[v] = 1; dfs1(v, v); hashes(v, v, 0);

	mp.clear();
	for (auto &to : gr[v]) {
		if (to == p || used[to]) continue;
		add(to, v, +1);
	}

	S = 1; cur_path[0] = v;
	for (auto &to : gr[v]) {
		if (to == p || used[to]) continue;
		add(to, v, -1);
		S = 1; if (dfs(to, v, l)) return 1;
		add(to, v, +1);
	}
	for (auto &to : gr[v]) {
		if (to == p || used[to]) continue;
		int c = centr(to, v, sz[to]);
		if (cd(c, v, l)) return 1;
	}
	return 0;
}

inline void solve() { calc();

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		char x;
		cin >> x;
		a[i] = x - 'a' + 1;
	}
	for (int i = 1; i < n; ++i) {
		int v, u;
		cin >> v >> u, --v, --u;
		gr[v].pb(u), gr[u].pb(v);
	}

	dfs1(0, 0);
	int C = centr(0, 0, n);

	int answer = 0;
	int l, r, m, ans;

	// even
	l = 1, r = n / 2, ans = 0;
	while (l <= r) {
		m = l + r >> 1;
		fill(used, used + n, 0);
		if (cd(C, C, 2 * m)) ans = m, l = m + 1;
		else r = m - 1;
	} chmax(answer, 2 * ans);

	// odd
	l = ans, r = (n - 1) / 2, ans = 0;
	while (l <= r) {
		m = l + r >> 1;
		fill(used, used + n, 0);
		if (cd(C, C, 2 * m + 1)) ans = m, l = m + 1;
		else r = m - 1;
	} chmax(answer, 2 * ans + 1);

	cout << answer;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

lampice.cpp: In function 'void solve()':
lampice.cpp:153:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |   m = l + r >> 1;
      |       ~~^~~
lampice.cpp:162:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |   m = l + r >> 1;
      |       ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1620 KB Output is correct
2 Correct 15 ms 1748 KB Output is correct
3 Correct 44 ms 1876 KB Output is correct
4 Correct 56 ms 1844 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2363 ms 9132 KB Output is correct
2 Correct 1697 ms 9664 KB Output is correct
3 Correct 445 ms 9520 KB Output is correct
4 Correct 686 ms 9800 KB Output is correct
5 Correct 2487 ms 10276 KB Output is correct
6 Correct 73 ms 8016 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4740 ms 8336 KB Output is correct
2 Correct 4305 ms 8788 KB Output is correct
3 Correct 4340 ms 8740 KB Output is correct
4 Correct 3323 ms 7212 KB Output is correct
5 Correct 2846 ms 8072 KB Output is correct
6 Correct 3131 ms 7796 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1620 KB Output is correct
2 Correct 15 ms 1748 KB Output is correct
3 Correct 44 ms 1876 KB Output is correct
4 Correct 56 ms 1844 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 2363 ms 9132 KB Output is correct
9 Correct 1697 ms 9664 KB Output is correct
10 Correct 445 ms 9520 KB Output is correct
11 Correct 686 ms 9800 KB Output is correct
12 Correct 2487 ms 10276 KB Output is correct
13 Correct 73 ms 8016 KB Output is correct
14 Correct 4740 ms 8336 KB Output is correct
15 Correct 4305 ms 8788 KB Output is correct
16 Correct 4340 ms 8740 KB Output is correct
17 Correct 3323 ms 7212 KB Output is correct
18 Correct 2846 ms 8072 KB Output is correct
19 Correct 3131 ms 7796 KB Output is correct
20 Correct 2193 ms 6324 KB Output is correct
21 Correct 2522 ms 7912 KB Output is correct
22 Correct 3598 ms 7920 KB Output is correct
23 Correct 730 ms 4912 KB Output is correct
24 Correct 3977 ms 6236 KB Output is correct
25 Correct 3122 ms 5988 KB Output is correct
26 Correct 4262 ms 8780 KB Output is correct
27 Correct 4750 ms 8296 KB Output is correct
28 Correct 2897 ms 4924 KB Output is correct
29 Correct 3122 ms 5036 KB Output is correct
30 Correct 3565 ms 6696 KB Output is correct
31 Correct 2545 ms 5980 KB Output is correct
32 Correct 2688 ms 7440 KB Output is correct
33 Correct 1757 ms 8100 KB Output is correct