Submission #1084862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084862		nmts	Lampice (COCI19_lampice)	C++17	17 / 110	5076 ms	8912 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;
basic_string<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 CD{

    int sz[maxn];
    bool del[maxn];

    void init()
        {
            memset(del , 0  , sizeof del);
        }

    void dfs(int u , int p)
        {

            sz[u] = 1;

            for (int v : edges[u])  
                if (v != p && del[v] == 0) 
                    {
                        dfs(v , u);
                        sz[u] += sz[v];
                    }

        }
    
    int find_centroid(int u , int p)
        {

            for (int v : edges[u])
                if (v != p)
                    if (sz[v] > n / 2 && del[v] == 0)
                        return find_centroid(v , u);

            return u;

        }

    bool get(int u , int p , int hight , int len)
        {

            hs.push(a[u]);

            if (2 * hight <= len && m[hs.get(hight)]) return 1;

            if (hight == len && hs.IsPalin(len)) return 1;

            for (int v : edges[u])
                if (v != p && del[v] == 0)
                    {
                        if (get(v , u , hight + 1 , len)) return 1;
                    }
            
            hs.pop();

            return 0;

        }
    
    bool update(int u , int p , int hight , int len)
        {

            hs.push(a[u]);

            if (hight * 2 >= len && hs.IsPalin(hight * 2 - len))
                m[hs.get(len - hight)] = 1;
            
            if (hight == len && hs.IsPalin(len)) return 1;

            for (int v : edges[u])
                if (v != p && del[v] == 0)  
                    {
                        if (update(v , u , hight + 1 , len)) return 1;
                    }
            hs.pop();

            return 0;

        }

    bool decompose(int u , int len)
        {

            dfs(u , 0);
            int c = find_centroid(u , 0);
            del[c] = 1;

                    m.clear();

                    for (int v : edges[c])
                        if (del[v] == 0)
                            {

                                hs.clear();

                                if (get(v , c , 1 , len)) return 1;

                                hs.clear();
                                hs.push(a[c]);

                                if (update(v , c , 2 , len)) return 1;

                            }

                    m.clear();

                    for (int i = edges[c].size() - 1 ; i >= 0 ; --i)
                        {
                            int v = edges[c][i];
                            if (del[v] == 0)
                                {

                                    hs.clear();

                                    if (get(v , c , 1 , len)) return 1;

                                    hs.clear();
                                    hs.push(a[c]);

                                    if (update(v , c , 2 , len)) return 1;

                                }
                        }

            for (int v : edges[u])
                if (del[v] == 0)
                    {
                        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:215:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  215 |             int mid = l + r >> 1;
      |                       ~~^~~

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