oj.uz

Submission #921149

# Submission time Handle Problem Language Result Execution time Memory
921149 2024-02-03T11:07:30 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 4977 ms 63300 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];
string s;
vector<int> g[N];
bool del[N];
unordered_map<int, bool> mp[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, int dep, int up, int down, bool &found) {
    up = (1ll * up * base + s[u] - 'a' + 1) % mod;
    down = (down + 1ll * Pow[dep - 1] * (s[u] - 'a' + 1)) % mod;
    int val = (1ll * down * Pow[len - dep] - up) % mod; if(val < 0) val += mod;
    if(upd) mp[dep][val] = 1;
    else {
        if(dep + 1 == len && up == (1ll * down * base + s[centroid] - 'a' + 1) % mod) {
            found = 1;
            return;
        }
        if(dep < len && mp[len - dep - 1][val]) {
            found = 1;
            return;
        }
    }
    if(dep < len) {
        for(int v : g[u]) if(v != p && !del[v])  {
            dfs_centroid(v, u, upd, dep + 1, up, down, found);
            mx = max(mx, dep + 1);
            if(found) return;
        }
    }
}
 
void calc(int u, bool &found) {
    centroid = find_centroid(u, 0, dfs_size(u));
    del[centroid] = 1;
    mx = 1;
    for(int v : g[centroid]) if(!del[v]) {
        dfs_centroid(v, centroid, 0, 1, s[centroid] - 'a' + 1, 0, found);
        if(found) return;
        dfs_centroid(v, centroid, 1, 1, s[centroid] - 'a' + 1, 0, found);
    }
    for(int i = 0; i <= mx; ++i) mp[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) mp[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:89:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 7 ms 4856 KB Output is correct
3 Correct 28 ms 5396 KB Output is correct
4 Correct 24 ms 4952 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 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 1523 ms 29804 KB Output is correct
2 Correct 2635 ms 48268 KB Output is correct
3 Correct 1315 ms 30920 KB Output is correct
4 Correct 1796 ms 32472 KB Output is correct
5 Correct 3852 ms 56732 KB Output is correct
6 Correct 180 ms 16552 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3028 ms 40524 KB Output is correct
2 Correct 4977 ms 55424 KB Output is correct
3 Correct 3857 ms 37436 KB Output is correct
4 Correct 2008 ms 13068 KB Output is correct
5 Correct 3500 ms 51052 KB Output is correct
6 Correct 2416 ms 30332 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 7 ms 4856 KB Output is correct
3 Correct 28 ms 5396 KB Output is correct
4 Correct 24 ms 4952 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1523 ms 29804 KB Output is correct
9 Correct 2635 ms 48268 KB Output is correct
10 Correct 1315 ms 30920 KB Output is correct
11 Correct 1796 ms 32472 KB Output is correct
12 Correct 3852 ms 56732 KB Output is correct
13 Correct 180 ms 16552 KB Output is correct
14 Correct 3028 ms 40524 KB Output is correct
15 Correct 4977 ms 55424 KB Output is correct
16 Correct 3857 ms 37436 KB Output is correct
17 Correct 2008 ms 13068 KB Output is correct
18 Correct 3500 ms 51052 KB Output is correct
19 Correct 2416 ms 30332 KB Output is correct
20 Correct 1259 ms 15584 KB Output is correct
21 Correct 2157 ms 41444 KB Output is correct
22 Correct 3989 ms 63300 KB Output is correct
23 Correct 451 ms 7608 KB Output is correct
24 Correct 2047 ms 21920 KB Output is correct
25 Correct 1641 ms 17232 KB Output is correct
26 Correct 2888 ms 32464 KB Output is correct
27 Correct 3382 ms 47920 KB Output is correct
28 Correct 1133 ms 7232 KB Output is correct
29 Correct 1210 ms 7448 KB Output is correct
30 Correct 1406 ms 11232 KB Output is correct
31 Correct 1214 ms 9768 KB Output is correct
32 Correct 1819 ms 31388 KB Output is correct
33 Correct 2811 ms 46656 KB Output is correct