| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 500920 |
2022-01-01T16:29:15 Z |
Duy_e |
Lampice (COCI19_lampice) |
C++14 |
|
2289 ms |
26768 KB |
#include <bits/stdc++.h>
#define debug cout << "fuck\n";
#define ll long long
#define ull unsigned long long
#define pii pair<long long, long long>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 2e5 + 5;
const long long base = 311;
const long long MOD = 2e9 + 7;
ll H[N], rH[N], pw[N], h[N], up[20][N];
vector <int> d[N], centroid;
string SS;
int n, numchild[N], s[N];
bool dead[N];
// find centroid
int get_size(int p, int u) {
int ans = 1;
for (int v: d[u]) if (v != p && !dead[v])
ans += get_size(u, v);
return ans;
}
int find_centroid(int S, int p, int u, int ma = 0) {
numchild[u] = 1;
for (int v: d[u]) if (v != p && !dead[v]) {
int get = find_centroid(S, u, v);
if (get != -1) return get;
numchild[u] += numchild[v];
ma = max(ma, numchild[v]);
}
ma = max(ma, S - numchild[u]);
return ma <= S/2 ? u: -1;
}
void FIND_CENTROID() {
queue <int> q; q.push(1);
while (q.size()) {
int u = q.front(); q.pop();
dead[u = find_centroid(get_size(0, u), 0, u)] = true;
centroid.push_back(u);
for (int v: d[u]) if (!dead[v]) q.push(v);
}
}
vector <int> save[N];
void dfs(int p, int u, int vi) {
for (int v: d[u]) if (v != p && !dead[v]) {
h[v] = h[u] + 1;
H[v] = (H[u]*base + s[v]) % MOD;
rH[v] = (rH[u] + pw[h[v]]*s[v]) % MOD;
up[0][v] = u;
for (int i = 1; (1 << i) <= h[v]; i ++)
up[i][v] = up[i - 1][up[i - 1][v]];
save[vi == 0 ? v : vi].push_back(v);
dfs(u, v, vi == 0 ? v : vi);
}
}
int kanc(int k, int u) {
int x = u;
for (int i = 19; i >= 0; i --)
if (k & 1 << i) u = up[i][u];
return u;
}
bool solve_len(int len, int u) {
// return true;
if (len <= 1) return true;
set <int> st, st2;
for (int vi: d[u]) if (!dead[vi]) {
for (int v: save[vi]) {
if (h[v] >= len) continue;
int mis = len - h[v] - 1;
if (st2.count((H[v] - H[u]*pw[h[v] - h[u]] + MOD * MOD) % MOD))
return true;
if (mis < 0) continue;
if (mis > h[v]) continue;
if (mis == 0) {
if (H[v] == rH[v]) return true;
continue;
}
int anc = kanc(mis - 1, v), anc2 = up[0][anc];
if (H[anc2] == rH[anc2]) {
ll get = (H[v] - H[anc2]*pw[h[v] - h[anc2]] + MOD * MOD) % MOD;
if (st.count(get)) return true;
}
}
for (int v: save[vi]) {
if (h[v] >= len) continue;
st.insert((H[v] - H[u]*pw[h[v] - h[u]] + MOD * MOD) % MOD);
{
int mis = len - h[v] - 1;
if (mis < 0) continue;
if (mis > h[v]) continue;
if (mis == 0) continue;
int anc = kanc(mis - 1, v), anc2 = up[0][anc];
if (H[anc2] == rH[anc2]) {
ll get = (H[v] - H[anc2]*pw[h[v] - h[anc2]] + MOD * MOD) % MOD;
st2.insert(get);
}
}
}
}
return false;
}
int bs(int x, int u) {
int l = 0, r = n, ans = x;
while (l <= r) {
int mid = l + r >> 1;
if (solve_len(mid * 2 + x, u))
ans = mid * 2 + x, l = mid + 1;
else
r = mid - 1;
}
return ans;
}
int solve(int u) {
H[u] = s[u]; rH[u] = s[u]; h[u] = 0;
dfs(u, u, 0);
ll ans = max(bs(1, u), bs(0, u));
for (int v: d[u]) save[v].clear();
return ans;
}
ll SOLVE_CENTROID() {
memset(dead, false, sizeof dead);
int ans = 0;
for (int u: centroid) {
dead[u] = true;
ans = max(ans, solve(u));
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> SS;
// s = ' ' + s;
for (int i = 1; i <= n; i ++)
s[i] = SS[i - 1] - 'a' + 1;
pw[0] = 1;
for (int i = 1; i < N; i ++)
pw[i] = pw[i - 1]*base % MOD;
for (int i = 1, u, v; i < n; i ++) {
cin >> u >> v;
d[u].push_back(v);
d[v].push_back(u);
}
FIND_CENTROID();
cout << SOLVE_CENTROID();
return 0;
}
/** /\_/\
(= ._.)
/ >🍵 \>🍮
________________________
/ Brainstorming section /
/=======================/
---
===
===
**/
// Before submit: spot the visible bug by reading the code.
Compilation message
lampice.cpp: In function 'int kanc(int, int)':
lampice.cpp:75:9: warning: unused variable 'x' [-Wunused-variable]
75 | int x = u;
| ^
lampice.cpp: In function 'int bs(int, int)':
lampice.cpp:136:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
136 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11596 KB |
Output is correct |
| 3 |
Correct |
24 ms |
11836 KB |
Output is correct |
| 4 |
Correct |
27 ms |
11852 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11468 KB |
Output is correct |
| 6 |
Correct |
6 ms |
11468 KB |
Output is correct |
| 7 |
Correct |
6 ms |
11468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1176 ms |
26768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1651 ms |
24872 KB |
Output is correct |
| 2 |
Correct |
1721 ms |
24300 KB |
Output is correct |
| 3 |
Correct |
1650 ms |
24308 KB |
Output is correct |
| 4 |
Correct |
2289 ms |
24984 KB |
Output is correct |
| 5 |
Correct |
1570 ms |
23052 KB |
Output is correct |
| 6 |
Correct |
1169 ms |
22220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11596 KB |
Output is correct |
| 3 |
Correct |
24 ms |
11836 KB |
Output is correct |
| 4 |
Correct |
27 ms |
11852 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11468 KB |
Output is correct |
| 6 |
Correct |
6 ms |
11468 KB |
Output is correct |
| 7 |
Correct |
6 ms |
11468 KB |
Output is correct |
| 8 |
Incorrect |
1176 ms |
26768 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
