oj.uz

Submission #1084876

# Submission time Handle Problem Language Result Execution time Memory
1084876 2024-09-07T06:47:04 Z nmts Lampice (COCI19_lampice) C++17
110 / 110
 3166 ms 13376 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;
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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1624 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 26 ms 1884 KB Output is correct
4 Correct 25 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1348 ms 9568 KB Output is correct
2 Correct 1079 ms 9692 KB Output is correct
3 Correct 682 ms 12888 KB Output is correct
4 Correct 878 ms 12900 KB Output is correct
5 Correct 1460 ms 13376 KB Output is correct
6 Correct 108 ms 9924 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2893 ms 11428 KB Output is correct
2 Correct 3166 ms 11252 KB Output is correct
3 Correct 2609 ms 11272 KB Output is correct
4 Correct 2207 ms 8620 KB Output is correct
5 Correct 1997 ms 10940 KB Output is correct
6 Correct 2096 ms 10500 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1624 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 26 ms 1884 KB Output is correct
4 Correct 25 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1348 ms 9568 KB Output is correct
9 Correct 1079 ms 9692 KB Output is correct
10 Correct 682 ms 12888 KB Output is correct
11 Correct 878 ms 12900 KB Output is correct
12 Correct 1460 ms 13376 KB Output is correct
13 Correct 108 ms 9924 KB Output is correct
14 Correct 2893 ms 11428 KB Output is correct
15 Correct 3166 ms 11252 KB Output is correct
16 Correct 2609 ms 11272 KB Output is correct
17 Correct 2207 ms 8620 KB Output is correct
18 Correct 1997 ms 10940 KB Output is correct
19 Correct 2096 ms 10500 KB Output is correct
20 Correct 1329 ms 7348 KB Output is correct
21 Correct 1553 ms 10424 KB Output is correct
22 Correct 2413 ms 10504 KB Output is correct
23 Correct 435 ms 4696 KB Output is correct
24 Correct 1943 ms 6572 KB Output is correct
25 Correct 1911 ms 6392 KB Output is correct
26 Correct 2490 ms 11660 KB Output is correct
27 Correct 2778 ms 10780 KB Output is correct
28 Correct 1425 ms 4644 KB Output is correct
29 Correct 1583 ms 4776 KB Output is correct
30 Correct 1687 ms 7020 KB Output is correct
31 Correct 1551 ms 6372 KB Output is correct
32 Correct 1223 ms 8924 KB Output is correct
33 Correct 1189 ms 10648 KB Output is correct