| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 526572 |
2022-02-15T09:34:39 Z |
tht2005 |
Lampice (COCI19_lampice) |
C++17 |
|
4155 ms |
11420 KB |
#include <bits/stdc++.h>
using namespace std;
int rd() {
bool neg = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') neg = !neg;
int n = 0; while('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
return neg ? -n : n;
}
void wr(int n) {
static char o[11];
if(n < 0) putchar('-'), n = -n;
int i = 0; do o[i++] = n % 10 + '0'; while(n /= 10);
while(i--) putchar(o[i]);
}
typedef unsigned long long LL;
const int N = 50005;
const int B = 311;
const int LG = 16;
int n, res;
char s[N];
vector<int> aj[N];
struct sub1 {
void dfs(int v, int p_, int d, LL pw, LL up, LL down) {
if(up == down && res < d)
res = d;
for(int u : aj[v]) {
if(u == p_) continue;
dfs(u, v, d + 1, pw * B, up + pw * s[u], down * B + s[u]);
}
}
sub1() {
for(int i = 1; i <= n; ++i)
dfs(i, -1, 1, B, s[i], s[i]);
}
};
struct sub4 {
int sz[N], dep[N], p[N][LG];
bool r[N], pal[N];
LL up[N], down[N], pw[N];
void dfs(int v, int p_) {
sz[v] = 1;
for(int u : aj[v]) {
if(u == p_ || r[u]) continue;
dfs(u, v);
sz[v] += sz[u];
}
}
int find_centroid(int v, int p_, int e) {
for(int u : aj[v]) {
if(u == p_ || r[u]) continue;
if(sz[u] > e) return find_centroid(u, v, e);
}
return v;
}
int getup(int v, int dd) {
for(int i = LG; i--; )
if(dd >> i & 1)
v = p[v][i];
return v;
}
set<LL> S;
bool go(int v, int p_, int L, bool o) {
if(dep[v] > L) return 0;
pal[v] = (down[v] == up[v]);
if(o) {
S.insert(down[v]);
}
else {
p[v][0] = p_;
for(int i = 0; i + 1 < LG; ++i)
if(p[v][i] < 0) p[v][i + 1] = -1;
else p[v][i + 1] = p[p[v][i]][i];
int dd = L - dep[v] + 1;
if(dd <= dep[v]) {
int x = getup(v, dd - 1);
if(pal[x]) {
x = p[x][0];
if(S.count(down[v] - down[x] * pw[dep[v] - dep[x]]))
return 1;
}
}
}
for(int u : aj[v]) {
if(u == p_ || r[u]) continue;
if(!o) {
dep[u] = dep[v] + 1;
up[u] = up[v] + pw[dep[v]] * s[u];
down[u] = down[v] * B + s[u];
}
if(go(u, v, L, o))
return 1;
}
return 0;
}
bool solve(int v, int L) {
dfs(v, -1);
v = find_centroid(v, -1, sz[v] >> 1);
r[v] = 1;
S.clear();
S.insert(s[v]);
pal[v] = 1;
dep[v] = 1;
up[v] = down[v] = s[v];
for(int u : aj[v]) {
if(r[u]) continue;
dep[u] = dep[v] + 1;
up[u] = up[v] + pw[dep[v]] * s[u];
down[u] = down[v] * B + s[u];
if(go(u, v, L, 0))
return 1;
go(u, v, L, 1);
}
for(int u : aj[v])
if(!r[u] && solve(u, L))
return 1;
return 0;
}
bool ck(int L) {
if(L <= n) {
for(int i = 1; i <= n; ++i)
r[i] = 0;
return solve(1, L);
}
return 0;
}
sub4() {
pw[0] = 1;
for(int i = 1; i < N; ++i)
pw[i] = pw[i - 1] * B;
for(int par = 0; par < 2; ++par) {
int ll = 1, rr = n;
while(ll <= rr) {
int m = (ll + rr) >> 1, L = m << 1 | par;
if(ck(L)) {
if(res < L) res = L;
ll = m + 1;
}
else
rr = m - 1;
}
}
}
};
int main() {
scanf("%d %s", &n, s + 1);
for(int i = 1; i < n; ++i) {
int u = rd(), v = rd();
aj[u].push_back(v);
aj[v].push_back(u);
}
res = 1;
delete new sub4;
wr(res);
return 0;
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%d %s", &n, s + 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1996 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1828 ms |
11420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4155 ms |
11076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1996 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
2124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
