Submission #530806

#	Time	Username	Problem	Language	Result	Execution time	Memory
530806		mat50013	Lampice (COCI19_lampice)	C++11	110 / 110	4915 ms	18424 KiB

lampice

#include <bits/stdc++.h>
#define d 256
#define MOD 1000000007
using namespace std;

/*
    Avem un arbore cu n noduri, fiecare nod initial are o culoare.
    Numim segment palindromic [u, v] daca lantul parcus de la u->v e acelasi cu cel parcus de la v->u
    Trebuie sa gasim cel mai lung segment palindromic.
*/

const int NMAX(50005);
using ll = long long;
ll putH[NMAX], h[NMAX], rh[NMAX];
bool dead[NMAX];
int cul[NMAX], sz[NMAX], n, toSearch[NMAX], nr, cat[NMAX], cnt, dp[NMAX][18], dist[NMAX], lg;
vector<int> G[NMAX], centroid, Grupa[NMAX];
bool viz[NMAX], can[NMAX];

inline void DFS(int nod)
{
    cat[nod] = cnt;
    viz[nod] = 1;
    for(auto it: G[nod])
        if(can[it] && !viz[it])
            DFS(it);
}

inline int getCentroid(int nod)
{
    viz[nod] = 1;
    sz[nod] = 1;
    int maxx = 0;
    for(auto it: G[nod])
        if(can[it] && !viz[it])
        {
            int c = getCentroid(it);
            if(c != -1)
                return c;
            sz[nod] += sz[it];
            maxx = max(maxx, sz[it]);
        }
    maxx = max(maxx, lg - sz[nod]);
    if(maxx <= lg / 2)
        return nod;
    return -1;
}

inline void precalcCentroid(vector<int> nodes)
{
    if(nodes.size() == 1)
    {
        centroid.push_back(nodes[0]);
        return;
    }
    lg = nodes.size();
    for(auto it: nodes)
        can[it] = 1, viz[it] = 0;
    int nd = getCentroid(nodes[0]);
    centroid.push_back(nd);
    for(auto it: nodes)
        viz[it] = 0;
    viz[nd] = 1;
    cnt = 0;
    for(auto it: G[nd])
        if(can[it])
        {
            ++cnt;
            DFS(it);
        }
    vector<vector<int> > unde(cnt + 1);
    for(auto it: nodes)
    {
        if(cat[it])
            unde[cat[it]].push_back(it);
        cat[it] = 0, can[it] = 0, viz[it] = 0;
    }
    int panaUnde = cnt;
    for(int i = 1;  i <= panaUnde; ++i)
        precalcCentroid(unde[i]);
}

inline void Precalc(int nod, int tata, int baseV = 0)
{
    for(int pt = 1; pt <= 17; ++pt)
        dp[nod][pt] = dp[dp[nod][pt - 1]][pt - 1];
    for(auto it: G[nod])
        if(it != tata && !dead[it])
        {
            dist[it] = dist[nod] + 1;
            h[it] = (d * h[nod] + cul[it]) % MOD;
            rh[it] = (rh[nod] + cul[it] * putH[dist[it]]) % MOD;
            dp[it][0] = nod;
            int val = (baseV == 0 ? it : baseV);
            Grupa[val].push_back(it);
            Precalc(it, nod, val);
        }
}

inline ll getHash(int st, int dr){
    return (h[dr] - h[st] * putH[dist[dr] - dist[st]] % MOD + MOD) % MOD;
}

int getDad(int nod, int dist){
    for(int put = 17; put >= 0; --put)
        if(dist - (1 << put) >= 0)
            nod = dp[nod][put], dist -= (1 << put);
    return nod;
}

inline bool calc(int nod, int lat)
{
    if(lat <= 1)
        return 1;
    h[nod] = rh[nod] = cul[nod], dist[nod] = 0;
    Precalc(nod, nod);
    set<ll> maiScurt, maiLung;
    maiScurt.insert(0), maiLung.insert(0);
    for(auto it: G[nod])
        if(!dead[it])
        {
            for(auto nd: Grupa[it]){
                int remDist = lat - dist[nd] - 1;
                if(remDist < 0)
                    continue;
                if(remDist >= dist[nd]){
                    if(maiLung.count(getHash(nod, nd)))
                        return 1;
                }
                else {
                    int bucataPal = getDad(nd, remDist);
                    if(h[bucataPal] == rh[bucataPal] && maiScurt.count(getHash(bucataPal, nd)))
                        return 1;
                }
            }
            for(auto nd: Grupa[it]){
                int remDist = lat - dist[nd] - 1;
                if(remDist < 0)
                    continue;
                if(remDist <= dist[nd])
                {
                    int bucataPal = getDad(nd, remDist);
                    if(h[bucataPal] == rh[bucataPal])
                        maiLung.insert(getHash(bucataPal, nd));
                }
                else maiScurt.insert(getHash(nod, nd));
            }
        }
    return 0;
}

inline bool solve(int lat)
{
    for(int i = 1; i <= n; ++i)
        dead[i] = 0;
    for(auto cen: centroid)
    {
        bool ok = calc(cen, lat);
        dead[cen] = 1;
        for(auto it: G[cen])
            Grupa[it].clear();
        if(ok)
            return 1;
    }
    return 0;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    string s;
    cin >> n >> s;

    vector<int> nodes;
    for(int i = 0; i < n; ++i)
        cul[i + 1] = (char)s[i], nodes.push_back(i + 1);

    for(int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    putH[0] = 1;
    for(int i = 1; i <= n; ++i)
        putH[i] = putH[i - 1] * d % MOD;
    precalcCentroid(nodes);

    int st = 1, dr = n / 2 + 1, best = 1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(solve(2 * mij))
        {
            best = 2 * mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    st = 1, dr = n / 2 + 1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(solve(2 * mij + 1))
        {
            best = max(best, 2 * mij + 1);
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    cout << best << '\n';
    return 0;
}

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