Submission #530460

#	Time	Username	Problem	Language	Result	Execution time	Memory
530460		mat50013	Lampice (COCI19_lampice)	C++11	0 / 110	5068 ms	9056 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];
int cul[NMAX], dist[NMAX], dp[NMAX][18], dad[NMAX];
vector<int> G[NMAX];
bool viz[NMAX];

inline void precalc(int nod)
{
    for(int pt = 1; pt <= 17; ++pt)
        if(dp[nod][pt - 1] != -1)
            dp[nod][pt] = dp[dp[nod][pt - 1]][pt - 1];
    viz[nod] = 1;
    for(auto it: G[nod])
        if(!viz[it])
        {
            dad[it] = nod;
            dp[it][0] = nod;
            h[it] = (h[nod] * d + cul[it]) % MOD;
            dist[it] = dist[nod] + 1;
            precalc(it);
        }
}

inline int LCA(int x, int y)
{
    if(dist[x] < dist[y])
        swap(x, y);
    for(int pt = 17; pt >= 0; --pt)
        if(dist[x] - (1 << pt) >= dist[y])
            x = dp[x][pt];
    if(x == y)
        return x;
    for(int pt = 17; pt >= 0; --    pt)
        if(dp[x][pt] != -1 && dp[y][pt] != -1 && dp[x][pt] != dp[y][pt])
            x = dp[x][pt], y = dp[y][pt];
    return dp[x][0];
}

inline int getD(int x, int dist)
{
    for(int pt = 17; pt >= 0; --pt)
        if(dist - (1 << pt) >= 0)
            x = dp[x][pt], dist -= (1 << pt);
    return x;
}

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

    int n;
    string s;
    cin >> n >> s;

    for(int i = 0; i < n; ++i)
        cul[i + 1] = s[i];

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

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

    for(int i = 1; i <= n; ++i)
        for(int pt = 0; pt <= 17; ++pt)
            dp[i][pt] = -1;
    dp[1][0] = 0;
    h[1] = cul[1];
    precalc(1);

    putH[0] = 1;
    for(int p = 1; p <= n; ++p)
        putH[p] = putH[p] * d % MOD;

    int maxx = 0;
    for(int nodS = 1; nodS <= n; ++nodS)
        for(int nodD = nodS + 1; nodD <= n; ++nodD)
        {
            int lc = LCA(nodS, nodD);
            if(nodS != lc && nodD != lc)
            {
                int st = nodS, dr = nodD;
                if(dist[st] > dist[dr])
                    swap(st, dr);
                ll h1 = (h[st] - h[dad[lc]] * putH[dist[dad[lc]]] % MOD + MOD) % MOD;
                int care = getD(dr, dist[st] - dist[lc] + 1);
                ll h2 = (h[dr] - h[care] * putH[dist[care]] % MOD + MOD) % MOD;
                //cerr << h1 << ' ' << h2 << '\n';
                if(h1 == h2)
                {
                    int i = getD(nodD, dist[nodD] - dist[lc] - 1);
                    int j = dad[care];
                    bool ok = 1;
                    while(dist[i] < dist[j])
                    {
                        if(cul[i] != cul[j])
                        {
                            ok = 0;
                            break;
                        }
                        ++i, --j;
                    }
                    if(ok)
                        maxx = max(maxx, dist[nodS] - dist[lc] + dist[nodD] - dist[lc] + 1);
                }
            }
            else
            {
                int st = nodS, dr = nodD;
                if(dist[st] > dist[dr])
                    swap(st, dr);
                bool ok = 1;
                while(dist[st] < dist[dr])
                {
                    if(cul[st] != cul[dr])
                    {
                        ok = 0;
                        break;
                    }
                    ++st, --dr;
                }
                if(ok)
                    maxx = max(maxx, abs(dist[nodD] - dist[nodS]) + 1);
            }

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

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