oj.uz

답안 #1084887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1084887 2024-09-07T06:54:17 Z nmts Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 8308 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, -1);
        int centroid = find_centroid(u, -1);
        del[centroid] = 1;
 
        for (int turn = 0; turn <= 1; ++turn)
        {
            m.clear();
            for (auto &v : edges[centroid])
            {
                if (del[v]) continue;
                
                hs.clear();
                if (get(v, centroid, 1, len)) 
                    return 1;
            
                hs.clear();
                hs.push(a[centroid]);
                if (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:196:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  196 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 7 ms 2072 KB Output is correct
3 Correct 104 ms 2204 KB Output is correct
4 Correct 128 ms 2136 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5024 ms 7560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5062 ms 8308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 7 ms 2072 KB Output is correct
3 Correct 104 ms 2204 KB Output is correct
4 Correct 128 ms 2136 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Execution timed out 5024 ms 7560 KB Time limit exceeded
9 Halted 0 ms 0 KB -