oj.uz

Submission #1084888

# Submission time Handle Problem Language Result Execution time Memory
1084888 2024-09-07T06:54:59 Z nmts Lampice (COCI19_lampice) C++17
110 / 110
 3136 ms 12956 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:181:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 28 ms 1884 KB Output is correct
4 Correct 25 ms 1628 KB Output is correct
5 Correct 1 ms 1624 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 1344 ms 9036 KB Output is correct
2 Correct 1078 ms 9144 KB Output is correct
3 Correct 691 ms 12192 KB Output is correct
4 Correct 891 ms 12312 KB Output is correct
5 Correct 1541 ms 12956 KB Output is correct
6 Correct 112 ms 9444 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2943 ms 10880 KB Output is correct
2 Correct 3136 ms 10652 KB Output is correct
3 Correct 2695 ms 10748 KB Output is correct
4 Correct 2231 ms 8064 KB Output is correct
5 Correct 2001 ms 10272 KB Output is correct
6 Correct 2079 ms 10008 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 28 ms 1884 KB Output is correct
4 Correct 25 ms 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1344 ms 9036 KB Output is correct
9 Correct 1078 ms 9144 KB Output is correct
10 Correct 691 ms 12192 KB Output is correct
11 Correct 891 ms 12312 KB Output is correct
12 Correct 1541 ms 12956 KB Output is correct
13 Correct 112 ms 9444 KB Output is correct
14 Correct 2943 ms 10880 KB Output is correct
15 Correct 3136 ms 10652 KB Output is correct
16 Correct 2695 ms 10748 KB Output is correct
17 Correct 2231 ms 8064 KB Output is correct
18 Correct 2001 ms 10272 KB Output is correct
19 Correct 2079 ms 10008 KB Output is correct
20 Correct 1384 ms 6796 KB Output is correct
21 Correct 1642 ms 10120 KB Output is correct
22 Correct 2411 ms 10140 KB Output is correct
23 Correct 436 ms 4120 KB Output is correct
24 Correct 2021 ms 6012 KB Output is correct
25 Correct 1888 ms 5804 KB Output is correct
26 Correct 2547 ms 11056 KB Output is correct
27 Correct 2752 ms 10148 KB Output is correct
28 Correct 1413 ms 3932 KB Output is correct
29 Correct 1531 ms 4188 KB Output is correct
30 Correct 1705 ms 6480 KB Output is correct
31 Correct 1550 ms 5720 KB Output is correct
32 Correct 1283 ms 8292 KB Output is correct
33 Correct 1194 ms 10148 KB Output is correct