oj.uz

Submission #640683

# Submission time Handle Problem Language Result Execution time Memory
640683 2022-09-15T05:52:18 Z LeonaRaging Lampice (COCI19_lampice) C++14
110 / 110
 4957 ms 15104 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
const ll base = 31;
const int N = 16;

int n, len, root, used[maxn], h[maxn];
string s;
vector<int> adj[maxn], nodes;
ll Pow[maxn], up[maxn], down[maxn];
gp_hash_table<ll,int> L;
bool flag;

ll add(ll a, ll b) {
    a += b;
    return a;
}

ll del(ll a, ll b) {
    a -= b;
    return a;
}

void pre(int u, int p) {
    if (p) 
        down[u] = add(down[p], (s[u] - 'a' + 1) * Pow[h[u] - 1]);
    if (p) 
        up[u] = add(up[p] * base, s[u] - 'a' + 1);
    L[up[u]]++;
    for (int v : adj[u])
        if (v != p && !used[v]) {
            h[v] = h[u] + 1;
            pre(v, u);
        }
}

void dfs(int u, int p) {
    if (len < h[u] || flag) return;
    nodes.pb(u);
    int k = len - h[u] - 1, c = 0;
    if (int(nodes.size()) > h[u] - k && h[u] - k >= 0)
        c = nodes[h[u] - k];
    if (c && add(up[c], (s[root] - 'a' + 1) * Pow[h[c]]) == 
            add(down[c] * base, (s[root] - 'a' + 1))) {
        if (k == 0)
            return flag = true, void();
        ll val = del(up[u], up[c] * Pow[k]) ;
        if (L.find(val) != L.end()) {
            return flag = true, void();
        }
    }
    for (int v : adj[u])
        if (v != p && !used[v])
            dfs(v, u);
    nodes.pop_back();
}

void reset(int u, int p, int val) {
    L[up[u]] += val;
    if (L[up[u]] == 0)
        L.erase(up[u]);
    for (int v : adj[u])
        if (v != p && !used[v])
            reset(v, u, val);
}

void Solve(int c) {
    h[c] = 0;
    up[c] = down[c] = 0;
    L.clear();
    pre(c, 0);
    nodes.clear();
    nodes.pb(c);
    for (int v : adj[c]) 
        if (!used[v]) {
            if (flag) return;
            reset(v, c, -1);
            dfs(v, c);
            reset(v, c, 1);
        }   
    nodes.pop_back();
}

struct Centroid_Decomposition {
    int sz[maxn];
    int dfs(int u, int p) {
        sz[u] = 1;
        for (int v : adj[u])
            if (!used[v] && v != p)
                sz[u] += dfs(v, u);
        return sz[u];
    }
    int Centroid(int u, int p, int tot) {
        for (int v : adj[u])
            if (!used[v] && v != p && sz[v] > tot / 2)
                return Centroid(v, u, tot);
        return u;
    }
    void build(int u) {
        if (flag) return;
        int c = Centroid(u, 0, dfs(u, 0));
        root = c;
        Solve(c);
        used[c] = 1;
        for (int v : adj[c])
            if (!used[v])
                build(v);
    }
} Cen;

bool ok(int m, int sign) {
    flag = false;
    len = 2 * m + sign;
    memset(used, 0, sizeof used);
    Cen.build(1);
    return flag;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    Pow[0] = 1;
    for (int i = 1; i <= n; i++) {
        Pow[i] = Pow[i - 1] * base;
    }
    // return cout << ok(2, 1), 0;
    int L = 1, R = n / 2, res = 1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (ok(mid, 1)) {
            res = 2 * mid + 1;
            L = mid + 1;
        }
        else R = mid - 1;
    }
    L = 1, R = n / 2;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (ok(mid, 0)) {
            res = max(res, 2 * mid);
            L = mid + 1;
        }
        else R = mid - 1;
    }
    cout << res;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3028 KB Output is correct
2 Correct 18 ms 3156 KB Output is correct
3 Correct 53 ms 3352 KB Output is correct
4 Correct 45 ms 3288 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2926 ms 14576 KB Output is correct
2 Correct 2017 ms 14592 KB Output is correct
3 Correct 1133 ms 14796 KB Output is correct
4 Correct 1346 ms 15028 KB Output is correct
5 Correct 2389 ms 15104 KB Output is correct
6 Correct 264 ms 12152 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4957 ms 13972 KB Output is correct
2 Correct 4484 ms 13692 KB Output is correct
3 Correct 4019 ms 13856 KB Output is correct
4 Correct 3702 ms 10996 KB Output is correct
5 Correct 3067 ms 13172 KB Output is correct
6 Correct 3093 ms 13228 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3028 KB Output is correct
2 Correct 18 ms 3156 KB Output is correct
3 Correct 53 ms 3352 KB Output is correct
4 Correct 45 ms 3288 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2926 ms 14576 KB Output is correct
9 Correct 2017 ms 14592 KB Output is correct
10 Correct 1133 ms 14796 KB Output is correct
11 Correct 1346 ms 15028 KB Output is correct
12 Correct 2389 ms 15104 KB Output is correct
13 Correct 264 ms 12152 KB Output is correct
14 Correct 4957 ms 13972 KB Output is correct
15 Correct 4484 ms 13692 KB Output is correct
16 Correct 4019 ms 13856 KB Output is correct
17 Correct 3702 ms 10996 KB Output is correct
18 Correct 3067 ms 13172 KB Output is correct
19 Correct 3093 ms 13228 KB Output is correct
20 Correct 2609 ms 10088 KB Output is correct
21 Correct 2852 ms 12972 KB Output is correct
22 Correct 3618 ms 13088 KB Output is correct
23 Correct 911 ms 6940 KB Output is correct
24 Correct 2909 ms 8928 KB Output is correct
25 Correct 2821 ms 8824 KB Output is correct
26 Correct 4011 ms 13880 KB Output is correct
27 Correct 4634 ms 13548 KB Output is correct
28 Correct 2546 ms 6964 KB Output is correct
29 Correct 2829 ms 7304 KB Output is correct
30 Correct 3172 ms 9296 KB Output is correct
31 Correct 2458 ms 8744 KB Output is correct
32 Correct 2230 ms 11056 KB Output is correct
33 Correct 1780 ms 13252 KB Output is correct