Submission #1084888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084888		nmts	Lampice (COCI19_lampice)	C++17	110 / 110	3136 ms	12956 KiB

lampice

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
 
#define endl '\n'    
#define ll long long
const int maxn = 5e4 + 6;
 
 
 
 
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
 
using namespace std;
using namespace __gnu_pbds;
const int base = 311;
 
int n;
vector<int> edges[maxn];
int ans = 1;
char a[maxn];
gp_hash_table<ll , bool> m;
 
struct Hash{
 
    ll pw[maxn] , hash_val[maxn] , pre_hash[maxn];
    int n ;
 
    void prepare(int sz)
        {
            n = 0;
            pw[0] = 1;
            
            for (int i = 1 ; i <= sz ; ++i)
                pw[i] = pw[i - 1] * base;
 
        }
 
    void push(char c)
        {
            n++;
 
            hash_val[n] = hash_val[n - 1] * base + c;
            pre_hash[n] = pre_hash[n - 1] + c * pw[n - 1];
 
        }
 
    void pop()
        {
            n--;
        }
    
    void clear()
        {
            n = 0;
        }
 
    bool IsPalin(int l)
        {
            return hash_val[l] == pre_hash[l];
        }
    
    ll get(int l)
        {
 
            return hash_val[n] - hash_val[n - l] * pw[l];
 
        }
 
 
} hs;
 
 
struct centroidDecomposition
{
    int sz[maxn];
    bool del[maxn];
 
    void init()
    {
        memset(del, 0, (n + 1) * sizeof(bool));
    }
 
    void dfs(int u, int p)
    {
        sz[u] = 1;
        for (auto &v : edges[u])
        {
            if (v == p || del[v]) continue;
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
 
    int findCentroid(int u, int p, int total)
    {
        for (auto &v : edges[u])
        {
            if (v == p || del[v]) continue;
            if (sz[v] > (total >> 1))
                return findCentroid(v, u, total);
        }
        return u;
    }
 
    bool dfs_update(int u, int p, int depth, int len)
    {
        hs.push(a[u]);
        if (depth * 2 >= len && hs.IsPalin(2 * depth - len)) //duong di qua goc tu 2 dinh con cach goc 1 khoang depth
            m[hs.get(len - depth)] = 1; 
        if (depth == len && hs.IsPalin(len))
            return 1;
        for (auto &v : edges[u])
        {
            if (v == p || del[v]) continue;
            if (dfs_update(v, u, depth + 1, len)) return 1;
        }
        hs.pop();
        return 0;
    }
 
    bool dfs_search(int u, int p, int depth, int len)
    {
        hs.push(a[u]);
        if (depth * 2 <= len && m[hs.get(depth)]) //chi 1 nhanh
            return 1;
        if (depth == len && hs.IsPalin(len))
            return 1;
        for (auto &v : edges[u])
        {
            if (v == p || del[v]) continue;
            if (dfs_search(v, u, depth + 1, len)) return 1;
        }
        hs.pop();
        return 0;
    }
 
    bool decompose(int u, int len)
    {
        dfs(u, -1);
        int centroid = findCentroid(u, -1, sz[u]);
        del[centroid] = 1;
 
        for (int turn = 0; turn <= 1; ++turn)
        {
            m.clear();
            for (auto &v : edges[centroid])
            {
                if (del[v]) continue;
                
                hs.clear();
                if (dfs_search(v, centroid, 1, len)) 
                    return 1;
            
                hs.clear();
                hs.push(a[centroid]);
                if (dfs_update(v, centroid, 2, len)) 
                    return 1;
            }
 
            reverse(edges[centroid].begin() , edges[centroid].end());
        }
 
        for (auto &v : edges[centroid])
        {
            if (del[v]) continue;
            if (decompose(v, len)) return 1;
        }
 
        return 0;
    }
} cd;
 
 
void tknp(int l , int r, int ok)
{
 
    while (l <= r ) 
        {
            int mid = l + r >> 1;
 
            cd.init();
 
            if (cd.decompose(1 , 2 * mid + ok)) maximize(ans  , 2 * mid + ok ) , l = mid + 1;
            else r = mid - 1;
 
        }
 
}
 
void solve()
{
 
 
    cin >> n ;
    hs.prepare(n + 1); 
 
    for (int i = 1 ; i <= n ; ++i) cin >> a[i];
 
    for (int i = 1 ; i < n ; ++i)
        {
            int u , v ; cin >> u >> v;
            edges[u].push_back(v);
            edges[v].push_back(u);
        } 
    
    tknp(1 , n >> 1 , 0);
    tknp(1 , n >> 1 , 1);
 
    cout << ans << endl;
 
}
 
 
int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
}

Compilation message (stderr)

lampice.cpp: In function 'void tknp(int, int, int)':
lampice.cpp:181:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |             int mid = l + r >> 1;
      |                       ~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37