Submission #223775

#	Time	Username	Problem	Language	Result	Execution time	Memory
223775		lyc	Lampice (COCI19_lampice)	C++14	17 / 110	4498 ms	17372 KiB

lampice

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#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;

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

const int P = 31337;//, Q = 1e9+7;
int pp[MX_N];
void init_hashing() {
    pp[0] = 1;
    FOR(i,1,N) pp[i] = 1LL*pp[i-1]*P;
}

int sub[MX_N], dad[MX_N];

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;
}

int dist[MX_N], hu[MX_N], hd[MX_N];
vector<int> nodes;
void dfs(int u, int p, int r, int d=0) {
    nodes.push_back(u);
    dist[u] = d;
    hu[u] = (hu[p] + 1LL * pp[dist[u]] * (S[u]-96));
    hd[u] = (1LL * hd[p] * P + (S[u]-96));
    //TRACE("dfs" _ u _ hu[u] _ hd[u] _ d);
    for (int v : al[u]) if (v != p and dad[v] == -1) {
        dfs(v,u,r,d+1);
    }
}

bool found;

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

    map<int,set<int>> hashes;
    for (auto v : al[c]) if (dad[v] == -1) {
        nodes.clear();
        dfs(v,c,c);
        //TRACE(c _ SZ(nodes));
        vector<pair<int,int>> tmp;
        for (int x : nodes) {
            //TRACE(x _ dist[x]+2);
            if (dist[x]+2 > len) continue;
            else if (dist[x]+2 == len) {
                int h1 = (1LL * hu[x] * P + (S[c]-96));
                int h2 = (hd[x] + 1LL * pp[dist[x]+1] * (S[c]-96));
                //TRACE(x _ dist[x] _ h1 _ h2 _ hu[x] _ hd[x]);
                //TRACE(dist[x]+1 _ pp[dist[x]+1]);
                found |= (h1 == h2);
            } else {
                int ky = len-1-(dist[x]+1);

                int hval = ((1LL * hu[x] * pp[ky + 1] - hd[x]) + 1LL * pp[ky] * (S[c]-96));
                //TRACE(x _ dist[x]+1 _ hval _ ky _ "::" _ hu[x] _ hd[x]);
                found |= hashes[ky].count(hval) > 0;
                tmp.emplace_back(dist[x]+1,hval);
            }
        }
        for (auto x : tmp) {
            hashes[x.first].insert(x.second);
        }

        decomp(v,c,len);
    }
}

bool solve(int len) {
    found = 0;
    memset(dad,-1,sizeof dad);
    decomp(1,0,len);
    return found;
}

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);
    }

    init_hashing();

    int ans = 0;
    { // odd
        int lo = 0, hi = (N+1)/2 + 1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            bool ok = solve(2*mid+1);
            if (ok) lo = mid;
            else hi = mid;
        }
        ans = max(ans,2*lo+1);
    }
    { // even
        int lo = 0, hi = (N+1)/2 + 1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            bool ok = solve(2*mid);
            if (ok) lo = mid;
            else hi = mid;
        }
        ans = max(ans,2*lo);
    }
    cout << ans << '\n';
}

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