oj.uz

Submission #640419

# Submission time Handle Problem Language Result Execution time Memory
640419 2022-09-14T15:25:10 Z LeonaRaging Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 19108 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 = 18;

int n, len, root, used[maxn], h[maxn], spt[maxn][20];
string s;
vector<int> adj[maxn];
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]]++;
    spt[u][0] = p;
    for (int j = 1; j <= N; j++)
        spt[u][j] = spt[spt[u][j - 1]][j - 1];
    for (int v : adj[u])
        if (v != p && !used[v]) {
            h[v] = h[u] + 1;
            pre(v, u);
        }
}

int jump(int u, int k) {
    for (int j = N; j >= 0; j--)
        if (k >> j & 1)
            u = spt[u][j];
    return u;
}

void dfs(int u, int p) {
    if (len < h[u]) return;
    int k = len - h[u] - 1, c = jump(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);
}

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);
    for (int v : adj[c]) 
        if (!used[v]) {
            reset(v, c, -1);
            dfs(v, c);
            reset(v, c, 1);
        }   
}

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;
    memset(used, 0, sizeof used);
    len = 2 * m + sign;
    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(4, 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 7 ms 3156 KB Output is correct
2 Correct 18 ms 3156 KB Output is correct
3 Correct 64 ms 3476 KB Output is correct
4 Correct 71 ms 3440 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 3843 ms 17124 KB Output is correct
2 Correct 2691 ms 17912 KB Output is correct
3 Correct 1613 ms 18120 KB Output is correct
4 Correct 1857 ms 18580 KB Output is correct
5 Correct 3183 ms 19108 KB Output is correct
6 Correct 491 ms 15916 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 17180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3156 KB Output is correct
2 Correct 18 ms 3156 KB Output is correct
3 Correct 64 ms 3476 KB Output is correct
4 Correct 71 ms 3440 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 3843 ms 17124 KB Output is correct
9 Correct 2691 ms 17912 KB Output is correct
10 Correct 1613 ms 18120 KB Output is correct
11 Correct 1857 ms 18580 KB Output is correct
12 Correct 3183 ms 19108 KB Output is correct
13 Correct 491 ms 15916 KB Output is correct
14 Execution timed out 5075 ms 17180 KB Time limit exceeded
15 Halted 0 ms 0 KB -