| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1084658 |
2024-09-06T16:02:50 Z |
anhthi |
Lampice (COCI19_lampice) |
C++14 |
|
3603 ms |
11060 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
template <class X, class Y>
inline bool maximize(X &x, Y y) {
return (x < y ? x = y, true : false);
}
template <class X, class Y>
inline bool minimize(X &x, Y y) {
return (x > y ? x = y, true : false);
}
template <class X>
inline void compress(vector<X> &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
return l + abs((ll) rng()) % (r - l + 1);
}
const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;
const int mxn = 5e4 + 10, mxm = 3e6;
const int LG = 18, BASE = 307;
int n;
char a[mxn + 5];
vector<int> g[mxn + 5];
int pw[mxn + 5];
namespace CTDL {
bool del[mxn + 5];
int childs[mxn + 5];
int getChilds(int u, int p) {
childs[u] = 1;
for (int v : g[u]) if (v != p && !del[v])
childs[u] += getChilds(v, u);
return childs[u];
}
int getCen(int u, int p, int sz) {
for (int v : g[u]) if (v != p && !del[v]) {
if (2 * childs[v] > sz) return getCen(v, u, sz);
}
return u;
}
int k;
bool ans;
int par[mxn + 5];
int f[mxn + 5], h[mxn + 5];
void prepare(int u, int p, int d = 1) {
if (ans) return;
if (d == k) {
if (f[u] == h[u]) ans = true;
return;
}
for (int v : g[u]) if (v != p && !del[v]) {
par[v] = u;
f[v] = (1LL * f[u] * BASE + a[v] - 'a' + 1) % mod;
h[v] = (1LL * (a[v] - 'a' + 1) * pw[d] + h[u]) % mod;
prepare(v, u, d + 1);
}
return;
}
gp_hash_table <int, bool> mark;
int node[mxn + 5];
void dfs(int u, int p, bool upd, int d = 2) {
if (ans) return;
if (d >= k) return;
node[d] = u;
if (upd) {
int rem = k - d;
if (d > rem) {
int v = node[d - rem];
if (f[v] == h[v])
ans = ans || mark[(f[u] - 1LL * f[par[v]] * pw[rem+1] + 1LL * mod * mod) % mod];
}
}
else mark[f[u]] = true;
for (int v : g[u]) if (v != p && !del[v])
dfs(v, u, upd, d + 1);
return;
}
void calc(int rt) {
par[rt] = 0; node[1] = rt;
f[rt] = h[rt] = a[rt] - 'a' + 1;
prepare(rt, 0);
if (ans) return;
rep(i, 2) {
mark.clear();
for (int v : g[rt]) if (!del[v]) {
dfs(v, rt, true);
if (!ans)
dfs(v, rt, false);
else return;
}
reverse(all(g[rt]));
}
return;
}
void solve(int u) {
int sz = getChilds(u, 0);
int cen = getCen(u, 0, sz);
calc(cen);
if (ans) return;
del[cen] = true;
for (int v : g[cen]) if (!del[v])
solve(v);
return;
}
bool ok(int _k) {
k = _k;
ans = false;
memset(del, 0, (n + 5) * sizeof (bool));
solve(1);
return ans;
}
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i, n) cin >> a[i];
rep(i, n - 1) {
int u, v;
cin >> u >> v;
g[u].pb(v); g[v].pb(u);
}
pw[0] = 1;
rep(i, n) pw[i] = 1LL * pw[i-1] * BASE % mod;
int ans = 1;
for (int l = 1, r = n / 2; l <= r; ) {
int m = (l + r) >> 1;
if (CTDL::ok(2 * m)) {
maximize(ans, 2 * m); l = m + 1;
}
else r = m - 1;
}
for (int l = 1, r = n / 2; l <= r; ) {
int m = (l + r) >> 1;
if (CTDL::ok(2 * m + 1)) {
maximize(ans, 2 * m + 1); l = m + 1;
}
else r = m - 1;
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1736 KB |
Output is correct |
| 3 |
Correct |
27 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
28 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1266 ms |
10160 KB |
Output is correct |
| 2 |
Correct |
1206 ms |
10236 KB |
Output is correct |
| 3 |
Correct |
750 ms |
10448 KB |
Output is correct |
| 4 |
Correct |
887 ms |
10996 KB |
Output is correct |
| 5 |
Correct |
1604 ms |
11060 KB |
Output is correct |
| 6 |
Correct |
137 ms |
9300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2645 ms |
8712 KB |
Output is correct |
| 2 |
Correct |
3603 ms |
8532 KB |
Output is correct |
| 3 |
Correct |
2937 ms |
8656 KB |
Output is correct |
| 4 |
Incorrect |
2265 ms |
7312 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1736 KB |
Output is correct |
| 3 |
Correct |
27 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
28 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 8 |
Correct |
1266 ms |
10160 KB |
Output is correct |
| 9 |
Correct |
1206 ms |
10236 KB |
Output is correct |
| 10 |
Correct |
750 ms |
10448 KB |
Output is correct |
| 11 |
Correct |
887 ms |
10996 KB |
Output is correct |
| 12 |
Correct |
1604 ms |
11060 KB |
Output is correct |
| 13 |
Correct |
137 ms |
9300 KB |
Output is correct |
| 14 |
Correct |
2645 ms |
8712 KB |
Output is correct |
| 15 |
Correct |
3603 ms |
8532 KB |
Output is correct |
| 16 |
Correct |
2937 ms |
8656 KB |
Output is correct |
| 17 |
Incorrect |
2265 ms |
7312 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
