Submission #223580

#	Time	Username	Problem	Language	Result	Execution time	Memory
223580		lyc	Lampice (COCI19_lampice)	C++14	0 / 110	5079 ms	13328 KiB

lampice

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 5e4+5;
const int P = 101;
const int Q = 1e9+7;

int N;
string S;
vector<int> al[MX_N];

int sub[MX_N], dad[MX_N];

int expo(int b, int p) {
    int r = 1;
    while (p > 0) {
        if (p&1) r = 1LL*r*b % Q;
        p >>= 1;
        b = 1LL*b*b % Q;
    }
    return r;
}

int subtree(int u, int p) {
    sub[u] = 1;
    for (auto v : al[u]) if (dad[v] == -1 and v != p) {
        sub[u] += subtree(v, u);
    }
    return sub[u];
}

int centroid(int u, int p, int sz) {
    for (auto v : al[u]) if (dad[v] == -1 and v != p and sub[v] > sz/2) {
        return centroid(v, u, sz);
    }
    return u;
}

bool ok;

int dist[MX_N], h1[MX_N], h2[MX_N];
vector<int> children;
void dfs(int u, int p) {
    children.push_back(u);
    h1[u] = (h1[p] + expo(P,dist[u]-1) * (S[u]-96) % Q) % Q;
    h2[u] = (1LL*h2[p]*P % Q + (S[u]-96)) % Q;
    for (auto v : al[u]) if (dad[v] == -1 and v != p) {
        dist[v] = dist[u] + 1;
        dfs(v,u);
    }
}

void solve(int u, int p, int tgt) {
    map<int,set<int>> hashes;
    h1[u] = h2[u] = 0;
    for (auto v : al[u]) if (dad[v] == -1 and v != p) {
        children.clear();
        dist[v] = 1; dfs(v,u);

        vector<pair<int,int>> tmp;
        for (auto& x : children) {
            if (dist[x] == tgt) {
                ok |= (h1[x] == h2[x]);
            } else if (dist[x] == tgt-1) {
                int v1 = ((h1[x] + 1LL * expo(P,dist[x]) * (S[u]-96) % Q) % Q);
                int v2 = ((1LL*h2[x]*P % Q + (S[u]-96)) % Q);
                ok |= (v1 == v2);
            } else {
                int kx = dist[x];
                int ky = tgt - 1 - kx;
                int hval = (1LL*expo(P,ky) * ((1LL*P*h1[x] % Q + (S[u]-96)) % Q) % Q - h2[x] + Q) % Q;
                if (hashes[ky].count(hval)) ok = 1;
                tmp.emplace_back(kx,hval);
            }
        }
        for (auto& x : tmp) hashes[x.first].insert(x.second);
    }
}

void reset() {
    ok = 0;
    memset(dad,-1,sizeof dad);
}

void decomp(int u, int p, int len) {
    if (ok) return;

    int sz = subtree(u, p);
    int c = centroid(u, p, sz);
    dad[c] = p;
    solve(c, p, len);

    for (auto v : al[c]) if (dad[v] == -1) {
        decomp(v, c, len);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    cin >> S; S = "^" + S;
    FOR(i,1,N-1){
        int A, B; cin >> A >> B;
        al[A].push_back(B);
        al[B].push_back(A);
    }

    int ans = 0;
    {// odd paths;
        int lo = -1, hi = (N+1)/2;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            //cout << "lo " << lo << " hi " << hi << " :: " << mid << endl;
            reset();
            decomp(1,0,2*mid+1);
            if (ok) lo = mid;
            else hi = mid;
        }
        //cout << "bleh " << 2*lo+1 << endl;
        ans = max(ans, 2*lo+1);
    }
    {// even paths;
        int lo = 0, hi = (N+3)/2;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            reset();
            decomp(1,0,2*mid);
            //cout << "try " << 2*mid << endl;
            if (ok) lo = mid;
            else hi = mid;
        }
        //cout << "bleh " << 2*lo << endl;
        ans = max(ans, 2*lo);
    }
    cout << ans << '\n';
}

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