| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1013175 |
2024-07-03T09:09:37 Z |
pan |
Lampice (COCI19_lampice) |
C++17 |
|
952 ms |
121280 KB |
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
// General
ll const P = 583726327;
ll const mod = 1000000007;
ll const MAXN = 50005;
ll n;
string s;
ll inv(ll a) {
return a <= 1 ? a : mod - (ll)(mod / a) * inv(mod % a) % mod;
}
// hashing: string to integer
ll conv[50], val[MAXN], ph[MAXN], invph[MAXN];
// centroid decomposition
ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN];
vector<ll> V[MAXN];
int dfs1(int u, int p, int l) {
sub[u] = 1; // Subtree size is 1
for (auto v : V[u]) {
if (lvl[v] != -1) continue; // Already added to centroid tree
if (v == p) continue;
sub[u] += dfs1(v, u, l); // Increase size of subtree
}
return sub[u];
}
int dfs2(int u, int p, int n) { // Pass in the size of the subtree
for (auto v : V[u]) {
if (lvl[v] != -1) continue; // Already added to centroid tree
if (v != p && sub[v] > n / 2) {
return dfs2(v, u, n); // DFS to that node
}
}
return u; // No child has size more than n/2, hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u, int p= -1, int l = 0) {
int n = dfs1(u, p, l); // Find the size of each subtree
int cent = dfs2(u, p, n); // Find the centroid
if (p == -1) p = cent; // Parent of root is yourself
par[cent] = p; // Set the parent of centroid to the previous centroid
lvl[cent] = l;
for (auto v : V[cent]) {
if (lvl[v] != -1) continue;
// If we have already added to centroid then we ignore
build(v, cent, l + 1); // Recursively build each subtree
}
}
//To construct the centroid tree, call build(root, -1, 0);
// precompute hash value
bool visited[MAXN];
ll locate[MAXN], up[MAXN], down[MAXN];
unordered_map<ll, unordered_map<ll, ll> > match[MAXN];
void mark(ll u, ll p, ll sub, ll cen, ll dep)
{
if (visited[u]) return;
locate[dep] = u;
down[u] = (down[p] + ph[dep]*val[u]%mod)%mod;
up[u] = (up[p]*P%mod + val[u])%mod;
ll line = (down[u] - val[cen] + mod)*invph[1]%mod;
if (match[cen][dep].count(line) &&match[cen][dep].count(line)!=sub )match[cen][dep][line] = -1;
else match[cen][dep][line] = sub;
for (ll x: V[u]) if (x!=p) mark(x, u, sub, cen,dep+1);
}
void precompute()
{
for (ll i=1; i<=n; ++i)
{
ll cur = i;
match[i][0][0] = -1;
down[i] = up[i] = val[i];
locate[0] = i;
while (par[cur]!=cur) {cur = par[cur], visited[cur] = 1;}
for (ll u: V[i]) mark(u, i, u, i, 1);
cur = i;
while (par[cur]!=cur) cur = par[cur], visited[cur] = 0;
}
}
// check whether palindrone of length x exists
bool search(ll u, ll p, ll sub, ll cen, ll dep, ll len)
{
if (visited[u]) return 0;
locate[dep] = u;
down[u] = (down[p] + ph[dep]*val[u]%mod)%mod;
up[u] = (up[p]*P%mod + val[u])%mod;
if (len/2 <= dep && dep < len) // ensure that the other end pass trhough centroid
{
ll over = len - (dep + 1);
ll pld = len - over*2;
if (up[locate[pld-1]] == down[locate[pld-1]])
{
ll line = (down[u] - down[locate[pld-1]] + mod)*invph[pld]%mod;
if (match[cen][over].count(line) && match[cen][over][line]!=sub) return 1;
}
}
for (ll x: V[u]) if (x!=p && search(x, u, sub, cen,dep+1, len)) return 1;
return 0;
}
bool check(ll x)
{
if (x < 2) return 1;
for (ll i=1; i<=n; ++i)
{
ll cur = i;
down[i] = up[i] = val[i];
locate[0] = i;
while (par[cur]!=cur) cur = par[cur], visited[cur] = 1;
for (ll u: V[i]) if (search(u, i, u, i, 1, x)) return 1;
cur = i;
while (par[cur]!=cur) cur = par[cur], visited[cur] = 0;
}
return 0;
}
int main()
{
// Input
input(n);
cin >> s;
for (ll i=0; i<n-1; ++i)
{
ll u, v;
input2(u, v);
V[u].pb(v);
V[v].pb(u);
}
// init
for (ll i=0; i<30; ++i) {conv[i] = rnd()%mod;}
for (ll i=0; i<n; ++i) val[i+1] = conv[s[i]-'a'];
ph[0]= invph[0] = 1;
for (ll i=1; i<=n; ++i)
{
ph[i] = ph[i-1]*P%mod;
invph[i] = inv(ph[i]);
}
fill(visited, visited+n+1, 0);
memset(lvl, -1, sizeof lvl);
build(1);
precompute();
// BSTA
ll ans = 0;
// Case1 : Even
ll lo = 0, hi = n;
while (lo!=hi)
{
ll mid = (lo+hi+1)/2;
if (check(mid*2)) lo = mid;
else hi = mid-1;
}
ans = max(ans, lo*2);
// Case 2: Odd
lo = 0, hi = n;
while (lo!=hi)
{
ll mid = (lo+hi+1)/2;
if (check(mid*2+1)) lo = mid;
else hi = mid-1;
}
ans = max(ans, lo*2+1);
print(ans, '\n');
return 0;
}
Compilation message
lampice.cpp: In function 'void mark(ll, ll, ll, ll, ll)':
lampice.cpp:106:63: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
106 | if (match[cen][dep].count(line) &&match[cen][dep].count(line)!=sub )match[cen][dep][line] = -1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
lampice.cpp:174:2: note: in expansion of macro 'input'
174 | input(n);
| ^~~~~
lampice.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
lampice.cpp:179:3: note: in expansion of macro 'input2'
179 | input2(u, v);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
105392 KB |
Output is correct |
| 2 |
Correct |
323 ms |
107952 KB |
Output is correct |
| 3 |
Correct |
387 ms |
110368 KB |
Output is correct |
| 4 |
Correct |
323 ms |
115604 KB |
Output is correct |
| 5 |
Correct |
379 ms |
121280 KB |
Output is correct |
| 6 |
Correct |
330 ms |
110768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
952 ms |
98644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
