| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1076171 |
2024-08-26T11:34:29 Z |
Ejen |
Lampice (COCI19_lampice) |
C++17 |
|
1753 ms |
17148 KB |
#include <bits/stdc++.h>
#define el "\n"
#define fu(i, a, b) for (int i = a; i <= b; ++i)
#define fd(i, a, b) for (int i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r) (rng);
}
ll last(ll msk) {return msk & (-msk);}
ll pop_cnt(ll msk) {return __builtin_popcountll(msk);}
ll ctz(ll msk) {return __builtin_ctzll(msk);}
ll lg(ll msk) {return 63 - __builtin_clzll(msk);}
template<class T1, class T2> bool minimize(T1 &a, T2 b) {
return a > b ? a = b, 1 : 0;
}
template<class T1, class T2> bool maximize(T1 &a, T2 b) {
return a < b ? a = b, 1 : 0;
}
template<class T> void print(T a) {
for (auto x : a) cout << x << " ";
cout << el;
}
template<class T> void compress(T &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
const long long N = 5e4 + 27, mod = 1e9 + 7, inf = 2e18, bl = 320, lim = 1e6 + 27;
const pair<ll, ll> base = make_pair(1000, 2000);
ll n, sz;
string s;
ll child[N], h[N];
pair<ll, ll> hashUp[N], hashDown[N], pw[N];
ll up[16][N];
bool del[N];
basic_string<ll> adj[N];
map<pair<ll, ll>, bool> mp;
pair<ll, ll> operator+(pair<ll, ll> x, pair<ll, ll> y) {return make_pair(x.ff + y.ff, x.ss + y.ss);}
pair<ll, ll> operator-(pair<ll, ll> x, pair<ll, ll> y) {return make_pair(x.ff - y.ff, x.ss - y.ss);}
pair<ll, ll> operator*(pair<ll, ll> x, pair<ll, ll> y) {return make_pair(x.ff * y.ff, x.ss * y.ss);}
pair<ll, ll> operator+(pair<ll, ll> x, char c) {return make_pair(x.ff + c, x.ss + c);}
pair<ll, ll> operator*(pair<ll, ll> x, char c) {return make_pair(x.ff * c, x.ss * c);}
void countChild(ll u, ll p) {
child[u] = 1;
// cout << u << ' ' << child[u] << el;
for (ll v : adj[u]) {
if (v == p || del[v]) continue;
countChild(v, u);
child[u] += child[v];
}
// cout << child[u] << ' ';
}
ll centroid(ll u, ll p, ll root) {
for (ll v : adj[u]) {
if (v == p || del[v] || child[v] <= child[root] / 2) continue;
return centroid(v, u, root);
}
return u;
}
ll lift(ll x, ll k) {
// if (x == 5) cout << k << el;
while (k) {
ll i = ctz(k);
x = up[i][x];
k -= last(k);
}
return x;
}
void dfs(ll u, ll p) {
hashUp[u] = hashUp[p] + pw[h[u]] * s[u];
hashDown[u] = hashDown[p] * base + s[u];
for (ll v : adj[u]) {
if (v == up[0][u] || del[v]) continue;
h[v] = h[u] + 1;
up[0][v] = u;
fu(i, 1, lg(h[v])) up[i][v] = up[i - 1][up[i - 1][v]];
dfs(v, u);
}
}
void dfsUpdate(ll u, ll len) {
if (len > h[u]) {
ll par = lift(u, len - h[u] - 1);
if (par && hashUp[par] == hashDown[par]) mp[hashDown[u] - hashDown[up[0][par]] * pw[h[u] - h[par] + 1]] = true;
}
for (ll v : adj[u]) {
if (v == up[0][u] || del[v]) continue;
dfsUpdate(v, len);
}
}
bool dfsSearch(ll u, ll len) {
if (mp[hashDown[u]]) return true;
if (h[u] + 1 == len && hashUp[u] == hashDown[u]) return true;
for (ll v : adj[u]) {
if (v == up[0][u] || del[v]) continue;
if (dfsSearch(v, len)) return true;
}
return false;
}
bool check(ll u, ll len) {
countChild(u, 0);
ll root = centroid(u, 0, u);
fu(i, 1, n) fu(j, 0, lg(n)) up[j][i] = 0;
h[root] = 0;
dfs(root, 0);
fu(turn, 0, 1) {
mp.clear();
reverse(all(adj[root]));
for (ll x : adj[root]) {
if (del[x]) continue;
if (dfsSearch(x, len)) return true;
dfsUpdate(x, len);
}
}
del[root] = true;
for (ll v : adj[root]) {
if (del[v]) continue;
return check(v, len);
}
return false;
}
signed main() {
// freopen("bai3.inp", "r", stdin);
// freopen("bai3.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> s;
s = ' ' + s;
sz = sz(s) - 1;
pw[0] = make_pair(1, 1);
fu(i, 1, n) pw[i] = pw[i - 1] * base;
fu(i, 2, n) {
ll u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// cout << check(1, 5);
ll res = 1;
ll l = 1, r = n / 2;
while (l <= r) {
ll mid = (r + l) / 2;
fu(i, 1, n) del[i] = 0;
if (check(1, 2 * mid)) {
res = 2 * mid;
l = mid + 1;
}
else r = mid - 1;
}
l = 1, r = n / 2;
while (l <= r) {
ll mid = (l + r) / 2;
fu(i, 1, n) del[i] = 0;
if (check(1, 2 * mid + 1)) {
maximize(res, 2 * mid + 1);
l = mid + 1;
}
else r = mid - 1;
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8796 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
3088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1353 ms |
17148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1753 ms |
16980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8796 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
3088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
