oj.uz

Submission #921135

# Submission time Handle Problem Language Result Execution time Memory
921135 2024-02-03T10:48:27 Z Beerus13 Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 56584 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];
int Pow[N];
string s;
vector<int> g[N];
bool del[N];
unordered_map<int, bool> mp[N];
int mx, centroid;

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, int len, 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, len, found);
            if(found) return;
        }
    }
}

void calc(int u, int len, 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, len, found);
        if(found) return;
        dfs_centroid(v, centroid, 1, 1, s[centroid] - 'a' + 1, 0, len, found);
    }
    for(int i = 0; i <= mx; ++i) mp[i].clear();
    for(int v : g[centroid]) if(!del[v]) {
        calc(v, len, found);
        if(found) return;
    }

}

bool check(int len) {
    for(int i = 0; i <= n; ++i) mp[i].clear();
    memset(del, 0, sizeof(del));
    bool found = 0;
    calc(1, len, 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, res = 0;
        while(r - l > 1) {
            int m = l + r >> 1;
            if(check(i + 2 * m)) res = i + 2 * m, l = m;
            else r = m;
        }
        ans = max(ans, res);
    }
    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:90:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 31 ms 5388 KB Output is correct
4 Correct 25 ms 4956 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4744 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1829 ms 29808 KB Output is correct
2 Correct 3338 ms 47888 KB Output is correct
3 Correct 1849 ms 30836 KB Output is correct
4 Correct 2664 ms 32408 KB Output is correct
5 Correct 4836 ms 56584 KB Output is correct
6 Correct 261 ms 16576 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3788 ms 40152 KB Output is correct
2 Correct 4743 ms 55084 KB Output is correct
3 Execution timed out 5024 ms 37932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 7 ms 4700 KB Output is correct
3 Correct 31 ms 5388 KB Output is correct
4 Correct 25 ms 4956 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4744 KB Output is correct
8 Correct 1829 ms 29808 KB Output is correct
9 Correct 3338 ms 47888 KB Output is correct
10 Correct 1849 ms 30836 KB Output is correct
11 Correct 2664 ms 32408 KB Output is correct
12 Correct 4836 ms 56584 KB Output is correct
13 Correct 261 ms 16576 KB Output is correct
14 Correct 3788 ms 40152 KB Output is correct
15 Correct 4743 ms 55084 KB Output is correct
16 Execution timed out 5024 ms 37932 KB Time limit exceeded
17 Halted 0 ms 0 KB -