Submission #1084842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084842		nmts	Lampice (COCI19_lampice)	C++17	0 / 110	5033 ms	8552 KiB

lampice

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define endl '\n'    
#define ll long long
const int maxn = 5e4 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

const int base = 311;
const int nmod = 2;
const ll modHash[4] = {(int)1e9 + 2277, (int)1e9 + 5277 , (int)1e9 + 8277 , (int)1e9 + 9277};


int n;
vector<int> edges[maxn];
int ans = 1;
char a[maxn];
map<pii , bool> m;

struct Hash{

    int pw[maxn][nmod] , hash_val[maxn][nmod] , pre_hash[maxn][nmod];
    int n ;

    void prepare()
        {
            n = 0;
            for (int i = 0 ; i < nmod ; ++i)
                pw[0][i] = 1;
            
            for (int i = 1 ; i <= 50000 ; ++i)
                for (int j = 0 ; j < nmod ; ++j)
                    pw[i][j] = pw[i - 1][j] * base % modHash[j];

        }

    void push(char c)
        {
            n++;
            for (int i = 0 ; i < nmod ;  ++i)
                hash_val[n][i] = (hash_val[n - 1][i] * base + c) % modHash[i],
                pre_hash[n][i] = (pre_hash[n - 1][i] + c * pw[n - 1][i]) % modHash[i];

        }

    void pop()
        {
            n--;
        }
    
    void clear()
        {
            n = 0;
        }

    bool IsPalin(int l)
        {
            return hash_val[l][1] == pre_hash[l][1] && hash_val[l][0] == pre_hash[l][0];
        }
    
    ll get(int l , int pos)
        {

            return hash_val[n][pos] - hash_val[n - l][pos] * pw[l][pos];

        }


} hs;


struct CD{

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

    void init()
        {
            for (int i = 1 ; i <= n ; ++i) del[i] = 0;
        }

    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 , 0)  , hs.get(hight , 1)}]) 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 , 0) , hs.get(len - hight , 1)}] = 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;

            for (int turn  = 1 ; turn <= 2 ; ++turn)
                {
                    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;

                            }
                    reverse(edges[c].begin() , edges[c].end());
                }       

            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)) ans = 2 * mid + ok  , l = mid + 1;
            else r = mid - 1;

        }

}

void solve()
{

    hs.prepare(); 

    cin >> n ;

    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:222:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  222 |             int mid = l + r >> 1;
      |                       ~~^~~

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