oj.uz

Submission #921147

# Submission time Handle Problem Language Result Execution time Memory
921147 2024-02-03T11:06:01 Z Beerus13 Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 56580 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) {
    mx = max(mx, dep);
    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);
            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 4696 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 28 ms 5224 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 1629 ms 29800 KB Output is correct
2 Correct 2624 ms 48044 KB Output is correct
3 Correct 1348 ms 30804 KB Output is correct
4 Correct 1824 ms 32424 KB Output is correct
5 Correct 4016 ms 56580 KB Output is correct
6 Correct 257 ms 16580 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2967 ms 40372 KB Output is correct
2 Execution timed out 5058 ms 55316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 28 ms 5224 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 1629 ms 29800 KB Output is correct
9 Correct 2624 ms 48044 KB Output is correct
10 Correct 1348 ms 30804 KB Output is correct
11 Correct 1824 ms 32424 KB Output is correct
12 Correct 4016 ms 56580 KB Output is correct
13 Correct 257 ms 16580 KB Output is correct
14 Correct 2967 ms 40372 KB Output is correct
15 Execution timed out 5058 ms 55316 KB Time limit exceeded
16 Halted 0 ms 0 KB -