oj.uz

Submission #211746

# Submission time Handle Problem Language Result Execution time Memory
211746 2020-03-21T06:39:15 Z VEGAnn Lampice (COCI19_lampice) C++14
110 / 110
 3224 ms 19448 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 50100;
const int PW = 233;
const int PO = 20;
const int md = 998244353;
__gnu_pbds::gp_hash_table<int, bool> mem[N];
vector<int> vc, g[N];
string s;
int ans = 0, kol, siz[N], mem_up[N], mem_down[N], po[N], inv[N], n, hsh[N][2], shsh[N], ANS[N][2];
bool mrk[N];

int mult(int x, int y) { return (1ll * x * y) % md; }

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int sub(int x, int y){
    x -= y;
    if (x < 0)
        x += md;
    return x;
}

int binpow(int x, int po){
    int res = 1;
    while (po > 0){
        if (po & 1)
            res = mult(res, x);

        x = mult(x, x);
        po >>= 1;
    }
    return res;
}

void build_sz(int v, int p){
    siz[v] = 1;
    for (int u : g[v]){
        if (u == p || mrk[u]) continue;
        build_sz(u, v);
        siz[v] += siz[u];
    }
}

int search(int v, int p, int SZ){
    for (int u : g[v])
        if (u != p && !mrk[u] && siz[u] > SZ / 2)
            return search(u, v, SZ);
    return v;
}

void calc_h(int v, int p, int h1, int h2, int shs, int ht){
    hsh[v][0] = h1;
    hsh[v][1] = h2;
    shsh[v] = shs;

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        int ch = s[u] - 'a' + 1;
        calc_h(u, v, sum(h1, mult(po[ht], ch)), sum(h2, mult(po[ht + 1], ch)), sum(ch, mult(PW, shs)), ht + 1);
    }
}

void change(int v, int p, int ht){
    mem[ht][hsh[v][0]] = 1;

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        change(u, v, ht + 1);
    }
}

void dfs(int v, int p, int ht, int len){
    if (ht + 1 > len) return;

    int hs = hsh[v][1];
    int shs = shsh[v];

    mem_up[ht] = shs;
    mem_down[ht] = hs;

    int c_len = len - (ht + 1);
    int c_ht = ht - c_len;

    if (c_ht >= 0){
        if (mem_up[c_ht] == mem_down[c_ht]) {
            int chs = sub(hs, mem_down[c_ht]);
            chs = mult(chs, inv[c_ht + 1]);

            if (mem[c_len].find(chs) != mem[c_len].end())
                kol++;
        }
    }

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        dfs(u, v, ht + 1, len);
    }
}

void check(int v, int p, int st){
    int l = 0, r = siz[v];

    while (l < r){
        int md = (l + r + 1) >> 1;
        int len = md + md + st;
        
        if (ANS[v][st] >= len){
            l = md;
            continue;
        }
        
        kol = 0;

        mem_up[0] = mem_down[0] = s[v] - 'a' + 1;

        for (int i = 1; i < siz[v]; i++)
            mem[i].clear();

        for (int u : g[v]){
            if (u == p || mrk[u]) continue;
            dfs(u, v, 1, len);
            change(u, v, 1);
        }

        for (int i = 1; i < siz[v]; i++)
            mem[i].clear();

        for (int it = sz(g[v]) - 1; it >= 0; it--){
            int u = g[v][it];
            if (u == p || mrk[u]) continue;
            dfs(u, v, 1, len);
            change(u, v, 1);
        }

        if (kol > 0)
            l = md;
        else r = md - 1;
    }

    ANS[v][st] = max(ANS[v][st], l + l + st);
    ans = max(ans, l + l + st);
}

void build_cd(int v, int p){
    build_sz(v, p);
    v = search(v, p, siz[v]);
    build_sz(v, p);

    mrk[v] = 1;
    for (int u : g[v])
        if (u != p && !mrk[u]) 
            build_cd(u, v);

    calc_h(v, p, 0, s[v] - 'a' + 1, s[v] - 'a' + 1, 0);
            
    check(v, p, 0);
    check(v, p, 1);

    if (p >= 0){
        ANS[p][0] = max(ANS[v][0], ANS[p][0]);
        ANS[p][1] = max(ANS[v][1], ANS[p][1]);
    }
    
    mrk[v] = 0;
}

int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("217.in","r",stdin);

    cin >> n >> s;

    po[0] = 1;
    for (int i = 1; i <= n; i++) {
        po[i] = mult(po[i - 1], PW);
        inv[i] = binpow(po[i], md - 2);
    }

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].PB(y);
        g[y].PB(x);
    }

    mem[0][0] = 1;
    build_cd(0, -1);

    cout << ans;

    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12160 KB Output is correct
2 Correct 23 ms 12160 KB Output is correct
3 Correct 49 ms 12288 KB Output is correct
4 Correct 51 ms 12288 KB Output is correct
5 Correct 17 ms 12160 KB Output is correct
6 Correct 16 ms 12192 KB Output is correct
7 Correct 16 ms 12160 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1253 ms 18552 KB Output is correct
2 Correct 1347 ms 18708 KB Output is correct
3 Correct 1594 ms 18644 KB Output is correct
4 Correct 1646 ms 19180 KB Output is correct
5 Correct 1564 ms 19448 KB Output is correct
6 Correct 1421 ms 19320 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2601 ms 17956 KB Output is correct
2 Correct 2453 ms 18024 KB Output is correct
3 Correct 2433 ms 17848 KB Output is correct
4 Correct 2831 ms 17124 KB Output is correct
5 Correct 2371 ms 17592 KB Output is correct
6 Correct 1754 ms 17144 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12160 KB Output is correct
2 Correct 23 ms 12160 KB Output is correct
3 Correct 49 ms 12288 KB Output is correct
4 Correct 51 ms 12288 KB Output is correct
5 Correct 17 ms 12160 KB Output is correct
6 Correct 16 ms 12192 KB Output is correct
7 Correct 16 ms 12160 KB Output is correct
8 Correct 1253 ms 18552 KB Output is correct
9 Correct 1347 ms 18708 KB Output is correct
10 Correct 1594 ms 18644 KB Output is correct
11 Correct 1646 ms 19180 KB Output is correct
12 Correct 1564 ms 19448 KB Output is correct
13 Correct 1421 ms 19320 KB Output is correct
14 Correct 2601 ms 17956 KB Output is correct
15 Correct 2453 ms 18024 KB Output is correct
16 Correct 2433 ms 17848 KB Output is correct
17 Correct 2831 ms 17124 KB Output is correct
18 Correct 2371 ms 17592 KB Output is correct
19 Correct 1754 ms 17144 KB Output is correct
20 Correct 1377 ms 16780 KB Output is correct
21 Correct 1646 ms 17780 KB Output is correct
22 Correct 2907 ms 17524 KB Output is correct
23 Correct 684 ms 16124 KB Output is correct
24 Correct 2708 ms 17016 KB Output is correct
25 Correct 2646 ms 16620 KB Output is correct
26 Correct 3224 ms 17908 KB Output is correct
27 Correct 3021 ms 17992 KB Output is correct
28 Correct 2229 ms 16100 KB Output is correct
29 Correct 2322 ms 16248 KB Output is correct
30 Correct 2822 ms 17272 KB Output is correct
31 Correct 2282 ms 16376 KB Output is correct
32 Correct 2292 ms 18400 KB Output is correct
33 Correct 1031 ms 18124 KB Output is correct