oj.uz

Submission #640420

# Submission time Handle Problem Language Result Execution time Memory
640420 2022-09-14T15:29:31 Z LeonaRaging Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 18664 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] || flag) 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]) {
            if (flag) return;
            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 6 ms 3160 KB Output is correct
2 Correct 18 ms 3156 KB Output is correct
3 Correct 60 ms 3480 KB Output is correct
4 Correct 60 ms 3532 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3096 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3704 ms 17320 KB Output is correct
2 Correct 2712 ms 17536 KB Output is correct
3 Correct 1515 ms 17796 KB Output is correct
4 Correct 1768 ms 17996 KB Output is correct
5 Correct 3156 ms 18664 KB Output is correct
6 Correct 382 ms 15332 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3160 KB Output is correct
2 Correct 18 ms 3156 KB Output is correct
3 Correct 60 ms 3480 KB Output is correct
4 Correct 60 ms 3532 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3096 KB Output is correct
8 Correct 3704 ms 17320 KB Output is correct
9 Correct 2712 ms 17536 KB Output is correct
10 Correct 1515 ms 17796 KB Output is correct
11 Correct 1768 ms 17996 KB Output is correct
12 Correct 3156 ms 18664 KB Output is correct
13 Correct 382 ms 15332 KB Output is correct
14 Execution timed out 5043 ms 17224 KB Time limit exceeded
15 Halted 0 ms 0 KB -