제출 #532225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532225		tibinyte	Lampice (COCI19_lampice)	C++14	0 / 110	5103 ms	17484 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
vector<int> centree[50001], g[50001];
bool color[50001], seen[50001];
int depth[50001], dp[50001], pater[50001], pater2[50001], power[50001], inv[50001], up[50001], down[50001], rmq[50001][18], n, p = 31, mod = 1000000007;
multiset<int> hashes[50001];
string s;
int powmod(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2 == 1) {
        return (1ll * a * powmod(a, b - 1));
    }
    int P = powmod(a, b / 2);
    return (P * P) % mod;
}
int invers(int a) {
    return powmod(a, mod - 2);
}
int get_size(int node, int parent) {
    if (seen[node]) {
        return 0;
    }
    dp[node] = 0;
    for (auto i : g[node]) {
        if (i != parent) {
            dp[node] += get_size(i, node);
        }
    }
    return ++dp[node];
}
int find_centroid(int node, int parent, int sz) {
    for (auto i : g[node]) {
        if (i != parent && !seen[i] && dp[i] > sz / 2) {
            return find_centroid(i, node, sz);
        }
    }
    return node;
}
void init_centroid(int node, int parent) {
    int qui = find_centroid(node, 0, get_size(node, 0));
    centree[parent].push_back(qui);
    centree[qui].push_back(parent);
    pater[qui] = parent;
    seen[qui] = true;
    for (auto i : g[qui]) {
        if (!seen[i]) {
            init_centroid(i, qui);
        }
    }
}
void paint(int node, bool flag) {
    function<void(int, int)> dfs = [&](int node, int parent) {
        color[node] = flag;
        for (auto i : centree[node]) {
            if (i != parent) {
                dfs(i, node);
            }
        }
    };
    dfs(node, pater[node]);
}
void dfs(int node, int parent, int d) {
    depth[node] = d;
    pater2[node] = parent;
    rmq[node][0] = parent;
    for (int i = 1; i <= 17; ++i) {
        rmq[node][i] = rmq[rmq[node][i - 1]][i - 1];
    }
    for (auto i : g[node]) {
        if (i != parent) {
            dfs(i, node, d + 1);
        }
    }
}
int anc(int node, int k) {
    for (int i = 17; i >= 0; --i) {
        if (k & (1 << i)) {
            node = rmq[node][i];
            k -= (1 << i);
        }
    }
    return node;
}
int get_depth(int node, int root) {
    return depth[node] - depth[root];
}
void compute_powers() {
    power[0] = 1;
    for (int i = 1; i <= 50000; ++i) {
        power[i] = (1ll * power[i - 1] * p) % mod;
    }
    int invp = invers(p);
    inv[0] = 1;
    for (int i = 1; i <= 50000; ++i) {
        inv[i] = (1ll * inv[i - 1] * invp) % mod;
    }
}
void compute_up(int root) {
    function<void(int, int, int)> dfs = [&](int node, int parent, int hash) {
        if (!color[node]) {
            return;
        }
        up[node] = ((1ll * hash * p) % mod + (s[node] - 'a' + 1)) % mod;
        for (auto i : g[node]) {
            if (i != parent) {
                dfs(i, node, up[node]);
            }
        }
    };
    dfs(root, 0, 0);
}
void compute_down(int root) {
    function<void(int, int, int)> dfs = [&](int node, int parent, int hash) {
        if (!color[node]) {
            return;
        }
        down[node] = hash + power[get_depth(node, root)] * (s[node] - 'a' + 1);
        for (auto i : g[node]) {
            if (i != parent) {
                dfs(i, node, up[node]);
            }
        }
    };
    dfs(root, 0, 0);
}
int hashup(int a, int b, int root) { // b e stramos al lui a !!!!
    if (b == root) {
        return up[a];
    }
    else {
        return (up[a] - (1ll * up[pater2[b]] * power[get_depth(a, root) - get_depth(b, root) + 1]) % mod + mod) % mod;
    }
}
int hashdown(int a, int b, int root) {
    if (b == root) {
        return down[a];
    }
    return (1ll * (down[a] - down[b] + mod) % mod * inv[get_depth(b, root)]) % mod;
}
bool palindrome(int a, int b, int root) {
    return hashup(a, b, root) == hashdown(a, b, root);
}
bool check(int root, int length) {
    paint(root, 1);
    function<void(int, int, int)> update = [&](int node, int parent, int d) {
        if (!color[node]) {
            return;
        }
        depth[node] = d;
        pater2[node] = parent;
        rmq[node][0] = parent;
        for (int i = 1; i <= 17; ++i) {
            rmq[node][i] = rmq[rmq[node][i - 1]][i - 1];
        }
        for (auto i : g[node]) {
            if (i != parent) {
                update(i, node, d + 1);
            }
        }
    };
    update(root, root, 0);
    compute_up(root);
    compute_down(root);
    function<void(int, int, int)> add = [&](int node, int parent, int subtree) {
        if (!color[node]) {
            return;
        }
        hashes[get_depth(node, root)].insert(hashup(node, subtree, root));
        for (auto i : g[node]) {
            if (i != parent) {
                add(i, node, subtree);
            }
        }
    };
    function<void(int, int, int)> rem = [&](int node, int parent, int subtree) {
        if (!color[node]) {
            return;
        }
        hashes[get_depth(node, root)].erase(hashes[get_depth(node, root)].find(hashup(node, subtree, root)));
        
        for (auto i : g[node]) {
            if (i != parent) {
                rem(i, node, subtree);
            }
        }
    };
    function<bool(int, int)> dfs = [&](int node, int parent) {
        if (!color[node]) {
            return false;
        }
        int d = get_depth(node, root) + 1;
        int req = length - d;
        bool ans = false;
        if (req > 0 && d >= req) {
            int hash = hashup(node, root, root);
            if (d == req) {

                ans = hashes[req].find(hash) != hashes[req].end();
            }
            else {
                int qui = anc(node, req);
                hash = hashup(node, anc(node, req - 1), root);
                ans = hashes[req].find(hash) != hashes[req].end() && palindrome(qui, root, root);
            }
        }
        for (auto i : g[node]) {
            if (i != parent) {
                ans |= dfs(i, node);
            }
        }
        return ans;
    };
    function<bool(int, int)> dfs2 = [&](int node, int parent) {
        if (!color[node]) {
            return false;
        }
        int d = get_depth(node, root) + 1;
        bool ok = false;
        if (d == length) {
            ok = palindrome(node, root, root);
        }
        for (auto i : g[node]) {
            if (i != parent) {
                ok |= dfs2(i, node);
            }
        }
        return ok;
    };

    bool ans = false;
    for (auto i : g[root]) {
        add(i, root, i);
    } 
    for (auto i : g[root]) {
        rem(i, root, i);
        ans |= dfs(i, root);
        add(i, root, i);
    }
    ans |= dfs2(root, 0);
    for (auto i : g[root]) {
        rem(i, root, i);
    }
    paint(root, 0);
    return ans;
}
bool check_centroids(int length) {
    for (int i = 1; i <= n; ++i) {
        if (check(i, length)) {
            return true;
        }
    }
    return false;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> s;
    s = '$' + s; // nu sunt colcalar
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    init_centroid(1, 0);
    dfs(1, 1, 0);
    compute_powers();
    int st = 1, dr = n, rep1 = 0, rep2 = 0;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (check_centroids(2 * mid)) {
            rep1 = mid;
            st = mid + 1;
        }
        else {
            dr = mid - 1;
        }
    }
    st = 1, dr = n;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (check_centroids(2 * mid + 1)) {
            rep2 = mid;
            st = mid + 1;
        }
        else {
            dr = mid - 1;
        }
    }
    cout << max({ rep1 * 2,rep2 * 2 + 1 });
}

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