oj.uz

Submission #921163

# Submission time Handle Problem Language Result Execution time Memory
921163 2024-02-03T11:28:51 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 1823 ms 14424 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 31;
 
int n, sz[N], Pow[N], dep[N], up[N], down[N];
string s;
vector<int> g[N];
bool del[N];
unordered_set<int> sett[N];
int mx, centroid, len;
 
int dfs_size(int u, int p = 0) {
    sz[u] = 1;
    for(int v : g[u]) if(v != p && !del[v]) {
        sz[u] += dfs_size(v, u);
    }
    return sz[u];
}
 
int find_centroid(int u, int p, int num) {
    for(int v : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num);
    return u;
}
 
void dfs_centroid(int u, int p, bool upd, bool &found) {
    dep[u] = dep[p] + 1;
    up[u] = (1ll * up[p] * base + s[u] - 'a' + 1) % mod;
    down[u] = (down[p] + 1ll * Pow[dep[u] - 1] * (s[u] - 'a' + 1)) % mod;
    int val = (1ll * down[u] * Pow[len - dep[u]] - up[u]) % mod; if(val < 0) val += mod;
    if(upd) sett[dep[u]].insert(val);
    else {
        if(dep[u] + 1 == len && up[u] == (1ll * down[u] * base + s[centroid] - 'a' + 1) % mod) {
            found = 1;
            return;
        }
        if(dep[u] < len && sett[len - dep[u] - 1].find(val) != sett[len - dep[u] - 1].end()) {
            found = 1;
            return;
        }
    }
    if(dep[u] < len) {
        for(int v : g[u]) if(v != p && !del[v])  {
            dfs_centroid(v, u, upd, found);
            mx = max(mx, dep[u] + 1);
            if(found) return;
        }
    }
}
 
void calc(int u, bool &found) {
    centroid = find_centroid(u, 0, dfs_size(u));
    del[centroid] = 1;
    mx = 1;
    up[centroid] = s[centroid] - 'a' + 1;
    down[centroid] = 0;
    dep[centroid] = 0;
    for(int v : g[centroid]) if(!del[v]) {
        dfs_centroid(v, centroid, 0, found);
        if(found) return;
        dfs_centroid(v, centroid, 1, found);
    }
    for(int i = 0; i <= mx; ++i) sett[i].clear();
    for(int v : g[centroid]) if(!del[v]) {
        calc(v, found);
        if(found) return;
    }
 
}
 
bool check(int x) {
    for(int i = 0; i <= n; ++i) sett[i].clear();
    memset(del, 0, sizeof(del));
    bool found = 0; len = x;
    calc(1, found);
    return found;
}
 
void solve() {
    cin >> n >> s; s = ' ' + s;
    Pow[0] = 1; for(int i = 1; i <= n; ++i) Pow[i] = (1ll * Pow[i - 1] * base) % mod;
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 1;
    for(int i = 0; i < 2; ++i) {
        int l = 0, r = n / 2 + 1;
        while(r - l > 1) {
            int m = l + r >> 1;
            if(check(i + 2 * m)) l = m;
            else r = m;
        }
        ans = max(ans, i + 2 * l);
    }
    cout << ans << '\n';
}
 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}
 
// https://oj.uz/problem/view/COCI19_lampice

Compilation message

lampice.cpp: In function 'void solve()':
lampice.cpp:93:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 18 ms 4896 KB Output is correct
4 Correct 23 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4540 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 13144 KB Output is correct
2 Correct 765 ms 13396 KB Output is correct
3 Correct 571 ms 13572 KB Output is correct
4 Correct 645 ms 13908 KB Output is correct
5 Correct 1062 ms 14424 KB Output is correct
6 Correct 152 ms 13400 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1489 ms 10384 KB Output is correct
2 Correct 1823 ms 9920 KB Output is correct
3 Correct 1569 ms 10644 KB Output is correct
4 Correct 1621 ms 10216 KB Output is correct
5 Correct 1142 ms 9308 KB Output is correct
6 Correct 1147 ms 9220 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 18 ms 4896 KB Output is correct
4 Correct 23 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4540 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 787 ms 13144 KB Output is correct
9 Correct 765 ms 13396 KB Output is correct
10 Correct 571 ms 13572 KB Output is correct
11 Correct 645 ms 13908 KB Output is correct
12 Correct 1062 ms 14424 KB Output is correct
13 Correct 152 ms 13400 KB Output is correct
14 Correct 1489 ms 10384 KB Output is correct
15 Correct 1823 ms 9920 KB Output is correct
16 Correct 1569 ms 10644 KB Output is correct
17 Correct 1621 ms 10216 KB Output is correct
18 Correct 1142 ms 9308 KB Output is correct
19 Correct 1147 ms 9220 KB Output is correct
20 Correct 943 ms 7748 KB Output is correct
21 Correct 1146 ms 8280 KB Output is correct
22 Correct 1606 ms 8904 KB Output is correct
23 Correct 365 ms 7004 KB Output is correct
24 Correct 1246 ms 8872 KB Output is correct
25 Correct 1213 ms 8220 KB Output is correct
26 Correct 1543 ms 10664 KB Output is correct
27 Correct 1600 ms 9128 KB Output is correct
28 Correct 1033 ms 7232 KB Output is correct
29 Correct 1084 ms 7512 KB Output is correct
30 Correct 1224 ms 9720 KB Output is correct
31 Correct 1057 ms 8212 KB Output is correct
32 Correct 1048 ms 10664 KB Output is correct
33 Correct 845 ms 8844 KB Output is correct