oj.uz

Submission #223580

# Submission time Handle Problem Language Result Execution time Memory
223580 2020-04-15T13:57:06 Z lyc Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 13328 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1792 KB Output is correct
2 Correct 19 ms 1792 KB Output is correct
3 Incorrect 63 ms 1920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 13328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5079 ms 9616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1792 KB Output is correct
2 Correct 19 ms 1792 KB Output is correct
3 Incorrect 63 ms 1920 KB Output isn't correct
4 Halted 0 ms 0 KB -