oj.uz

Submission #530806

# Submission time Handle Problem Language Result Execution time Memory
530806 2022-02-26T20:48:29 Z mat50013 Lampice (COCI19_lampice) C++11
110 / 110
 4915 ms 18424 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 12 ms 2812 KB Output is correct
3 Correct 37 ms 3020 KB Output is correct
4 Correct 42 ms 3208 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2360 ms 15496 KB Output is correct
2 Correct 2286 ms 16508 KB Output is correct
3 Correct 1610 ms 17936 KB Output is correct
4 Correct 1837 ms 18424 KB Output is correct
5 Correct 2954 ms 18288 KB Output is correct
6 Correct 599 ms 17804 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4329 ms 16856 KB Output is correct
2 Correct 4915 ms 17064 KB Output is correct
3 Correct 4090 ms 16440 KB Output is correct
4 Correct 3288 ms 16180 KB Output is correct
5 Correct 3034 ms 15640 KB Output is correct
6 Correct 3037 ms 14492 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 12 ms 2812 KB Output is correct
3 Correct 37 ms 3020 KB Output is correct
4 Correct 42 ms 3208 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 2360 ms 15496 KB Output is correct
9 Correct 2286 ms 16508 KB Output is correct
10 Correct 1610 ms 17936 KB Output is correct
11 Correct 1837 ms 18424 KB Output is correct
12 Correct 2954 ms 18288 KB Output is correct
13 Correct 599 ms 17804 KB Output is correct
14 Correct 4329 ms 16856 KB Output is correct
15 Correct 4915 ms 17064 KB Output is correct
16 Correct 4090 ms 16440 KB Output is correct
17 Correct 3288 ms 16180 KB Output is correct
18 Correct 3034 ms 15640 KB Output is correct
19 Correct 3037 ms 14492 KB Output is correct
20 Correct 2551 ms 13368 KB Output is correct
21 Correct 3011 ms 14364 KB Output is correct
22 Correct 3709 ms 15700 KB Output is correct
23 Correct 1311 ms 12640 KB Output is correct
24 Correct 3159 ms 15180 KB Output is correct
25 Correct 2895 ms 14860 KB Output is correct
26 Correct 3674 ms 16952 KB Output is correct
27 Correct 4103 ms 16644 KB Output is correct
28 Correct 2352 ms 14308 KB Output is correct
29 Correct 2515 ms 14720 KB Output is correct
30 Correct 2970 ms 15880 KB Output is correct
31 Correct 2578 ms 14856 KB Output is correct
32 Correct 2387 ms 16564 KB Output is correct
33 Correct 2164 ms 15668 KB Output is correct