oj.uz

Submission #1108015

# Submission time Handle Problem Language Result Execution time Memory
1108015 2024-11-02T14:57:13 Z atom Lampice (COCI19_lampice) C++17
110 / 110
 1682 ms 45336 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 5e4 + 5;
const int BASE = 256;
const int MOD = 1e9 + 7;

int n, k;
string a;
int sz[N];
bool rem[N];
vector <int> adj[N];
int pw[N];
 
int dfsSZ(int u, int p) {
    sz[u] = 1;
    for (int v: adj[u]) if (v != p && !rem[v]) {
        sz[u] += dfsSZ(v, u);
    }
    return sz[u];
}
 
int findCentroid(int u, int p, int n) {
    for (int v: adj[u]) if (v != p && !rem[v]) {
        if (2 * sz[v] > n)
            return findCentroid(v, u, n);
    }
    return u;
}
 
int h[N];
int maxHigh;
int hashU[N];
int hashD[N];
int value[N];
int nNode, node[N];
map<int, bool> mp[N];
 
void add(int u, int p, bool &found) {
    h[u] = h[p] + 1;
    if (h[u] + 1 > k) return;
    maxHigh = max(maxHigh, h[u]);
    hashU[u] = (1LL * hashU[p] * BASE + (a[u] - 'a' + 1)) % MOD;
    hashD[u] = (hashD[p] + 1LL * pw[h[u]] * (a[u] - 'a' + 1)) % MOD;
    int need = (1LL * pw[k - h[u] - 1] * hashD[u] - hashU[u] + MOD) % MOD;
    if (mp[k - h[u] - 1].find(need) != mp[k - h[u] - 1].end()) {
        found = true;
        return;
    }
    if (h[u] + 1 == k && hashD[u] == (hashU[u] + 1LL * pw[h[u]] * (a[u] - 'a' + 1)) % MOD) {
        found = true;
        return;
    }
    node[++nNode] = u; value[u] = need;
    for (int v: adj[u]) if (v != p && !rem[v]) {
        add(v, u, found);
        if (found) return;
    }
}
 
void solve(int u, int p, bool &found) {
    int n = dfsSZ(u, p), c = findCentroid(u, p, n); rem[c] = true;

    h[c] = 0;
    nNode = 0;
    maxHigh = 0;
    hashU[c] = 0;
    hashD[c] = a[c] - 'a' + 1;
    for (int v: adj[c]) if (v != p && !rem[v]) {
        add(v, c, found);
        if (found) return;
        while (nNode > 0) {
            int u = node[nNode--];
            mp[h[u]][value[u]] = 1;
        }
    }
    for (int i = 0; i <= maxHigh; ++i) {
        mp[i].clear();
    }
 
    for (int v: adj[c]) if (v != p && !rem[v]) {
        solve(v, c, found);
        if (found) return;
    }
}
 
bool func(int x) {
    memset(rem, false, sizeof rem);
    bool found = false; k = x;
    solve(1, 0, found);
    return found;
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
 
    cin >> n >> a;
    a = "@" + a;

    for (int i = 1; i < n; ++i) {
    	int u, v;
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
    	pw[i] = (1LL * pw[i - 1] * BASE) % MOD;
    }

   	int ans = 1;
    for (int i = 0; i <= 1; ++i) {
        int l = 0, r = n / 2 + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (func(i + 2 * mid)) 
            	l = mid; 
            else 
            	r = mid;
        }
        ans = max(ans, i + 2 * l);
    }
    cout << ans << "\n";

    return 0;
}

// Centroid: path of equal length

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5200 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 16 ms 5344 KB Output is correct
4 Correct 15 ms 5200 KB Output is correct
5 Correct 2 ms 5112 KB Output is correct
6 Correct 2 ms 5200 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 11508 KB Output is correct
2 Correct 612 ms 12904 KB Output is correct
3 Correct 415 ms 23364 KB Output is correct
4 Correct 530 ms 23368 KB Output is correct
5 Correct 814 ms 13648 KB Output is correct
6 Correct 189 ms 45336 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 10136 KB Output is correct
2 Correct 1665 ms 9880 KB Output is correct
3 Correct 1461 ms 9928 KB Output is correct
4 Correct 1223 ms 10840 KB Output is correct
5 Correct 1101 ms 14348 KB Output is correct
6 Correct 1039 ms 9172 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5200 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 16 ms 5344 KB Output is correct
4 Correct 15 ms 5200 KB Output is correct
5 Correct 2 ms 5112 KB Output is correct
6 Correct 2 ms 5200 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 608 ms 11508 KB Output is correct
9 Correct 612 ms 12904 KB Output is correct
10 Correct 415 ms 23364 KB Output is correct
11 Correct 530 ms 23368 KB Output is correct
12 Correct 814 ms 13648 KB Output is correct
13 Correct 189 ms 45336 KB Output is correct
14 Correct 1279 ms 10136 KB Output is correct
15 Correct 1665 ms 9880 KB Output is correct
16 Correct 1461 ms 9928 KB Output is correct
17 Correct 1223 ms 10840 KB Output is correct
18 Correct 1101 ms 14348 KB Output is correct
19 Correct 1039 ms 9172 KB Output is correct
20 Correct 1052 ms 9316 KB Output is correct
21 Correct 1315 ms 10936 KB Output is correct
22 Correct 1682 ms 9980 KB Output is correct
23 Correct 365 ms 7240 KB Output is correct
24 Correct 1044 ms 8548 KB Output is correct
25 Correct 992 ms 8396 KB Output is correct
26 Correct 1333 ms 10056 KB Output is correct
27 Correct 1654 ms 9192 KB Output is correct
28 Correct 715 ms 7240 KB Output is correct
29 Correct 767 ms 7176 KB Output is correct
30 Correct 911 ms 9544 KB Output is correct
31 Correct 789 ms 7752 KB Output is correct
32 Correct 889 ms 12336 KB Output is correct
33 Correct 946 ms 9296 KB Output is correct