oj.uz

Submission #921165

# Submission time Handle Problem Language Result Execution time Memory
921165 2024-02-03T11:31:46 Z Beerus13 Lampice (COCI19_lampice) C++14
110 / 110
 1862 ms 14428 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_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 3 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 18 ms 4700 KB Output is correct
4 Correct 19 ms 4884 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 819 ms 13148 KB Output is correct
2 Correct 809 ms 13540 KB Output is correct
3 Correct 526 ms 13396 KB Output is correct
4 Correct 653 ms 13948 KB Output is correct
5 Correct 1046 ms 14428 KB Output is correct
6 Correct 171 ms 13732 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1520 ms 10380 KB Output is correct
2 Correct 1862 ms 9920 KB Output is correct
3 Correct 1713 ms 10644 KB Output is correct
4 Correct 1569 ms 10204 KB Output is correct
5 Correct 1208 ms 9452 KB Output is correct
6 Correct 1147 ms 9232 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 18 ms 4700 KB Output is correct
4 Correct 19 ms 4884 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 819 ms 13148 KB Output is correct
9 Correct 809 ms 13540 KB Output is correct
10 Correct 526 ms 13396 KB Output is correct
11 Correct 653 ms 13948 KB Output is correct
12 Correct 1046 ms 14428 KB Output is correct
13 Correct 171 ms 13732 KB Output is correct
14 Correct 1520 ms 10380 KB Output is correct
15 Correct 1862 ms 9920 KB Output is correct
16 Correct 1713 ms 10644 KB Output is correct
17 Correct 1569 ms 10204 KB Output is correct
18 Correct 1208 ms 9452 KB Output is correct
19 Correct 1147 ms 9232 KB Output is correct
20 Correct 950 ms 7744 KB Output is correct
21 Correct 1110 ms 8512 KB Output is correct
22 Correct 1556 ms 9048 KB Output is correct
23 Correct 348 ms 7116 KB Output is correct
24 Correct 1328 ms 8868 KB Output is correct
25 Correct 1191 ms 8212 KB Output is correct
26 Correct 1604 ms 10432 KB Output is correct
27 Correct 1627 ms 9124 KB Output is correct
28 Correct 1014 ms 7252 KB Output is correct
29 Correct 1118 ms 7504 KB Output is correct
30 Correct 1226 ms 9724 KB Output is correct
31 Correct 1051 ms 8228 KB Output is correct
32 Correct 1087 ms 10920 KB Output is correct
33 Correct 822 ms 8628 KB Output is correct