oj.uz

Submission #921158

# Submission time Handle Problem Language Result Execution time Memory
921158 2024-02-03T11:17:34 Z Beerus13 Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 57392 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_map<int, bool> mp[N];
int mx, centroid, len;
vector<int> node;

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) {
    node.push_back(u);
    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) mp[dep[u]][val] = 1;
    else {
        if(dep[u] + 1 == len && up[u] == (1ll * down[u] * base + s[centroid] - 'a' + 1) % mod) {
            found = 1;
            return;
        }
        if(dep[u] < len && mp[len - dep[u] - 1][val]) {
            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;
    node.clear();
    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 v : node) {
        mp[dep[v]].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:98:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             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 8 ms 4892 KB Output is correct
3 Correct 32 ms 5432 KB Output is correct
4 Correct 28 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 2 ms 4700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1772 ms 30424 KB Output is correct
2 Correct 2821 ms 48888 KB Output is correct
3 Correct 1505 ms 31456 KB Output is correct
4 Correct 1879 ms 33408 KB Output is correct
5 Correct 3974 ms 57392 KB Output is correct
6 Correct 196 ms 17356 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3653 ms 41036 KB Output is correct
2 Execution timed out 5028 ms 56020 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 4700 KB Output is correct
2 Correct 8 ms 4892 KB Output is correct
3 Correct 32 ms 5432 KB Output is correct
4 Correct 28 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 2 ms 4700 KB Output is correct
8 Correct 1772 ms 30424 KB Output is correct
9 Correct 2821 ms 48888 KB Output is correct
10 Correct 1505 ms 31456 KB Output is correct
11 Correct 1879 ms 33408 KB Output is correct
12 Correct 3974 ms 57392 KB Output is correct
13 Correct 196 ms 17356 KB Output is correct
14 Correct 3653 ms 41036 KB Output is correct
15 Execution timed out 5028 ms 56020 KB Time limit exceeded
16 Halted 0 ms 0 KB -