oj.uz

Submission #1084858

# Submission time Handle Problem Language Result Execution time Memory
1084858 2024-09-07T06:16:59 Z nmts Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 8940 KB 
#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()
        {
            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)]) 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;

            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)) 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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 3 ms 1892 KB Output is correct
3 Correct 56 ms 2276 KB Output is correct
4 Correct 56 ms 2140 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 2040 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 8120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 8940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 3 ms 1892 KB Output is correct
3 Correct 56 ms 2276 KB Output is correct
4 Correct 56 ms 2140 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 2040 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Execution timed out 5072 ms 8120 KB Time limit exceeded
9 Halted 0 ms 0 KB -