oj.uz

Submission #921151

# Submission time Handle Problem Language Result Execution time Memory
921151 2024-02-03T11:10:36 Z Beerus13 Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 56528 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 = 331;

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 4696 KB Output is correct
2 Correct 7 ms 4696 KB Output is correct
3 Correct 27 ms 5212 KB Output is correct
4 Correct 24 ms 5208 KB Output is correct
5 Correct 1 ms 4736 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 1643 ms 29748 KB Output is correct
2 Correct 2688 ms 47780 KB Output is correct
3 Correct 1393 ms 30564 KB Output is correct
4 Correct 1579 ms 32120 KB Output is correct
5 Correct 3576 ms 56528 KB Output is correct
6 Correct 211 ms 16576 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3082 ms 40268 KB Output is correct
2 Execution timed out 5002 ms 55292 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 4696 KB Output is correct
3 Correct 27 ms 5212 KB Output is correct
4 Correct 24 ms 5208 KB Output is correct
5 Correct 1 ms 4736 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1643 ms 29748 KB Output is correct
9 Correct 2688 ms 47780 KB Output is correct
10 Correct 1393 ms 30564 KB Output is correct
11 Correct 1579 ms 32120 KB Output is correct
12 Correct 3576 ms 56528 KB Output is correct
13 Correct 211 ms 16576 KB Output is correct
14 Correct 3082 ms 40268 KB Output is correct
15 Execution timed out 5002 ms 55292 KB Time limit exceeded
16 Halted 0 ms 0 KB -