oj.uz

Submission #223410

# Submission time Handle Problem Language Result Execution time Memory
223410 2020-04-15T08:53:04 Z lyc Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 153000 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];
vector<tuple<int,int,int>> pth[MX_N];
vector<int> g[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;

void solve(int u, int p, int tgt) {
    pth[u].clear();
    pth[u].emplace_back(0,0,0);

    map<int,set<int>> hashes;
    for (auto v : al[u]) if (dad[v] == -1 and v != p) {
        solve(v,u,tgt);

        vector<pair<int,int>> tmp;
        for (auto& x : pth[v]) {
            int len, h1, h2; tie(len,h1,h2) = x;
            h1 = ((1LL * h1 * P) % Q + (S[v]-96)) % Q; // v to c
            h2 = (h2 + 1LL * (S[v]-96) * expo(P, len) % Q) % Q;    // c to v
            len += 1;
            pth[u].emplace_back(len,h1,h2);

            if (len == tgt && h1 == h2) ok = 1;

            int kx = len;
            int ky = tgt - 1 - kx;
            int hval = (1LL*expo(P,ky) * ((1LL*P*h1 % Q + (S[u]-96)) % Q) % Q - h2 + Q) % Q;
            if (hashes[ky].count(hval)) ok = 1;
            tmp.emplace_back(kx,hval);
            //cout << "centroid " << u << " -> " << v << " :: " << hval << endl;
        }
        for (auto& x : tmp) hashes[x.first].insert(x.second);
    }

    sort(pth[u].begin(), pth[u].end());
}

void reset() {
    ok = 0;
    memset(dad,-1,sizeof dad);
    FOR(i,1,N) g[i].clear();
}

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;
    g[p].push_back(c);
    solve(c, p, len);

    //cout << "c " << c << " "  << SZ(g[c]) << " :: ";
    //for (auto x : pth[c]) {
    //    cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << " || ";
    //}
    //cout << endl;

    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;
            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+1)/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 23 ms 4096 KB Output is correct
2 Correct 57 ms 4224 KB Output is correct
3 Correct 804 ms 5472 KB Output is correct
4 Correct 1323 ms 6752 KB Output is correct
5 Incorrect 7 ms 4096 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5086 ms 151228 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 5066 ms 153000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4096 KB Output is correct
2 Correct 57 ms 4224 KB Output is correct
3 Correct 804 ms 5472 KB Output is correct
4 Correct 1323 ms 6752 KB Output is correct
5 Incorrect 7 ms 4096 KB Output isn't correct
6 Halted 0 ms 0 KB -