oj.uz

Submission #923030

# Submission time Handle Problem Language Result Execution time Memory
923030 2024-02-06T13:01:34 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 1956 ms 12884 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];
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;
    mx = max(mx, dep[u]);
    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);
            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 4 ms 4696 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 21 ms 4892 KB Output is correct
4 Correct 20 ms 4700 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 751 ms 11864 KB Output is correct
2 Correct 715 ms 11772 KB Output is correct
3 Correct 482 ms 11980 KB Output is correct
4 Correct 619 ms 12512 KB Output is correct
5 Correct 983 ms 12884 KB Output is correct
6 Correct 112 ms 11512 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1495 ms 10580 KB Output is correct
2 Correct 1930 ms 10128 KB Output is correct
3 Correct 1672 ms 10348 KB Output is correct
4 Correct 1467 ms 9560 KB Output is correct
5 Correct 1217 ms 9640 KB Output is correct
6 Correct 1175 ms 9248 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 21 ms 4892 KB Output is correct
4 Correct 20 ms 4700 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 751 ms 11864 KB Output is correct
9 Correct 715 ms 11772 KB Output is correct
10 Correct 482 ms 11980 KB Output is correct
11 Correct 619 ms 12512 KB Output is correct
12 Correct 983 ms 12884 KB Output is correct
13 Correct 112 ms 11512 KB Output is correct
14 Correct 1495 ms 10580 KB Output is correct
15 Correct 1930 ms 10128 KB Output is correct
16 Correct 1672 ms 10348 KB Output is correct
17 Correct 1467 ms 9560 KB Output is correct
18 Correct 1217 ms 9640 KB Output is correct
19 Correct 1175 ms 9248 KB Output is correct
20 Correct 1202 ms 7972 KB Output is correct
21 Correct 1449 ms 8768 KB Output is correct
22 Correct 1915 ms 9132 KB Output is correct
23 Correct 439 ms 7308 KB Output is correct
24 Correct 1290 ms 8432 KB Output is correct
25 Correct 1247 ms 8048 KB Output is correct
26 Correct 1590 ms 10000 KB Output is correct
27 Correct 1956 ms 9448 KB Output is correct
28 Correct 994 ms 7332 KB Output is correct
29 Correct 1097 ms 7392 KB Output is correct
30 Correct 1173 ms 8912 KB Output is correct
31 Correct 1048 ms 8004 KB Output is correct
32 Correct 1012 ms 9900 KB Output is correct
33 Correct 1119 ms 9268 KB Output is correct