| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 486774 |
2021-11-12T18:22:49 Z |
jalsol |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
12224 KB |
#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
using namespace std;
static const bool __initialization = []() {
cin.tie(nullptr)->sync_with_stdio(false);
#define TASK "empty"
if (fopen(TASK".inp", "r")) {
(void)(!freopen(TASK".inp", "r", stdin));
(void)(!freopen(TASK".out", "w", stdout)); }
return true;
}();
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)
template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }
constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
// =============================================================================
namespace KACTL {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wshadow"
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
// content goes here
struct H {
typedef uint64_t ull;
ull x; H(ull x=0) : x(x) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
(A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx")
H operator-(H o) { return *this + ~o.x; }
ull get() const { return x + !~x; }
bool operator==(H o) const { return get() == o.get(); }
bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)
struct HashInterval {
vector<H> ha, pw;
HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
pw[0] = 1;
rep(i,0,sz(str))
ha[i+1] = ha[i] * C + str[i],
pw[i+1] = pw[i] * C;
}
H hashInterval(int a, int b) { // hash [a, b)
return ha[b] - ha[a] * pw[b - a];
}
};
vector<H> getHashes(string& str, int length) {
if (sz(str) < length) return {};
H h = 0, pw = 1;
rep(i,0,length)
h = h * C + str[i], pw = pw * C;
vector<H> ret = {h};
rep(i,length,sz(str)) {
ret.push_back(h = h * C + str[i] - pw * str[i-length]);
}
return ret;
}
H hashString(string& s){H h{}; for(char c:s) h=h*C+c;return h;}
// content ends here
#undef rep
#undef sz
#undef pii
#undef vi
#pragma GCC diagnostic pop
} // namespace KACTL
using namespace KACTL;
constexpr int maxn = 5e4 + 5;
constexpr int logn = 20;
constexpr int base = 31;
int n;
char a[maxn];
vector<int> g[maxn];
H power[maxn];
H hdown[maxn], hup[maxn];
bool found;
bool rem[maxn];
int sz[maxn];
int up[maxn][logn];
int dep[maxn];
vector<int> node;
vector<pair<H, int>> layer[maxn];
void getSz(int u, int p) {
sz[u] = 1;
Fe (v : g[u]) {
if (rem[v] || v == p) continue;
getSz(v, u);
sz[u] += sz[v];
}
}
int getCen(int target, int u, int p) {
Fe (v : g[u]) {
if (rem[v] || v == p) continue;
if (sz[v] * 2 > target) return getCen(target, v, u);
}
return u;
}
void prepare(int u, int p) {
node.push_back(u);
layer[dep[u]].emplace_back(hdown[u], u);
For (i, 1, logn - 1) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
Fe (v : g[u]) {
if (rem[v] || v == p) continue;
up[v][0] = u;
dep[v] = dep[u] + 1;
hdown[v] = hdown[u] * base + (a[v] - 'a' + 1);
hup[v] = hup[u] + power[dep[v] - 1] * (a[v] - 'a' + 1);
prepare(v, u);
}
}
int lift(int u, int dist) {
Repd (i, logn) {
if (dist >> i & 1) u = up[u][i];
}
return u;
}
int getLca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int dist = dep[u] - dep[v];
u = lift(u, dist);
if (u == v) return u;
Repd (i, logn) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
H getHash(int u, int v) {
return hdown[u] - hdown[up[v][0]] * power[dep[u] - dep[v] + 1];
}
void calc(int u, int len) {
if (found) return;
hdown[u] = a[u] - 'a' + 1;
hup[u] = a[u] - 'a' + 1;
node.clear();
up[u][0] = 0;
dep[u] = 1;
prepare(u, -1);
For (i, 1, n) {
sort(all(layer[i]));
}
Fe (A : node) {
if (found) break;
int odist = len - dep[A] + 1;
if (odist > dep[A] || odist < 1) continue;
const auto& cur = layer[odist];
int C = lift(A, odist - 1);
if (hdown[C].x != hup[C].x) continue;
H ohash = getHash(A, C);
auto it = lower_bound(all(cur), pair(ohash, -1));
if (it == cur.end()) {
continue;
}
while (it != cur.end()) {
if (it->fi.x != ohash.x) break;
int B = it->se;
if (getLca(A, B) == u) {
found = true;
break;
} else {
++it;
}
}
}
For (i, 1, n) {
layer[i].clear();
}
}
void cd(int u, int len) {
if (found) return;
getSz(u, -1);
u = getCen(sz[u], u, -1);
rem[u] = true;
calc(u, len);
for (int v : g[u]) {
if (rem[v] == false) {
cd(v, len);
}
}
}
bool check(int len) {
found = false;
memset(rem, false, sizeof(rem));
cd(1, len);
return found;
}
signed main() {
cin >> n >> (a + 1);
Rep (_, n - 1) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
power[0] = 1;
For (i, 1, n) power[i] = power[i - 1] * base;
int l, r;
int ans = 0;
l = 0, r = n / 2;
while (l <= r) {
int m = (l + r) / 2;
if (check(2 * m + 1)) {
l = m + 1;
} else {
r = m - 1;
}
}
chmax(ans, 2 * r + 1);
l = 1, r = n / 2;
while (l <= r) {
int m = (l + r) / 2;
if (check(2 * m)) {
l = m + 1;
} else {
r = m - 1;
}
}
chmax(ans, 2 * r);
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3916 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4032 KB |
Output is correct |
| 3 |
Correct |
78 ms |
4044 KB |
Output is correct |
| 4 |
Correct |
138 ms |
4240 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3788 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3788 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5085 ms |
12224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5053 ms |
11960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3916 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4032 KB |
Output is correct |
| 3 |
Correct |
78 ms |
4044 KB |
Output is correct |
| 4 |
Correct |
138 ms |
4240 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3788 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3788 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3788 KB |
Output is correct |
| 8 |
Execution timed out |
5085 ms |
12224 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
