oj.uz

Submission #1076555

# Submission time Handle Problem Language Result Execution time Memory
1076555 2024-08-26T14:43:07 Z Ejen Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 14800 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define el "\n"
#define fu(i, a, b) for (int i = a; i <= b; ++i)
#define fd(i, a, b) for (int i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)
 
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
ll Rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r) (rng);
}
 
ll last(ll msk)     {return msk & (-msk);}
ll pop_cnt(ll msk)  {return __builtin_popcountll(msk);}
ll ctz(ll msk)      {return __builtin_ctzll(msk);}
ll lg(ll msk)       {return 63 - __builtin_clzll(msk);}
 
template<class T1, class T2> bool minimize(T1 &a, T2 b) {
    return a > b ? a = b, 1 : 0;
}
 
template<class T1, class T2> bool maximize(T1 &a, T2 b) {
    return a < b ? a = b, 1 : 0;
}
 
template<class T> void print(T a) {
    for (auto x : a) cout << x << " ";
    cout << el;
}
 
template<class T> void compress(T &a) {
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
}
 
const long long N = 5e4 + 27, mod = 1e9 + 7, inf = 2e18, bl = 320, lim = 1e6 + 27, base = 311;
 
int n, sz;
string s;
int child[N], h[N];
ll hashUp[N], hashDown[N], pw[N];
int up[16][N];
bool del[N];
basic_string<int> adj[N];
gp_hash_table<ll, bool> mp;
 
void countChild(int u, int p) {
    child[u] = 1;
    // cout << u << ' '  << child[u] << el;
    for (int v : adj[u]) {
        if (v == p || del[v]) continue;
        countChild(v, u);
        child[u] += child[v];
    }
    // cout << child[u] << ' ';
}
 
int centroid(int u, int p, int root) {
    for (int v : adj[u]) {
        if (v == p || del[v] || child[v] <= child[root] / 2) continue;
        return centroid(v, u, root);
    }
    return u;
}
 
int lift(int x, int k) {
    // if (x == 5) cout << k << el;
    while (k) {
        int i = ctz(k);
        x = up[i][x];
        k -= last(k);
    }
    return x;
}
 
void dfs(int u, int p) {
    hashUp[u] = hashUp[p] + s[u] * pw[h[u]];
    hashDown[u] = hashDown[p] * base + s[u];
    for (int v : adj[u]) {
        if (v == up[0][u] || del[v]) continue;
        h[v] = h[u] + 1;
        up[0][v] = u;
        fu(i, 1, lg(h[v])) up[i][v] = up[i - 1][up[i - 1][v]];
        dfs(v, u);
    }
}
 
void dfsUpdate(int u, int len) {
    if (len > h[u]) {
        int par = lift(u, len - h[u] - 1);
        if (par && hashUp[par] == hashDown[par]) mp[hashDown[u] - hashDown[up[0][par]] * pw[h[u] - h[par] + 1]] = true;
    }
    for (int v : adj[u]) {
        if (v == up[0][u] || del[v]) continue;
        dfsUpdate(v, len);
    }
}
 
bool dfsSearch(int u, int len) {
    if (mp[hashDown[u]]) return true;
    if (h[u] + 1 == len && hashUp[u] == hashDown[u]) return true;
    for (int v : adj[u]) {
        if (v == up[0][u] || del[v]) continue;
        if (dfsSearch(v, len)) return true;
    }
    return false;
}
 
bool check(int u, int len) {
    countChild(u, 0);
    int root = centroid(u, 0, u);
    fu(i, 1, n) fu(j, 0, lg(n)) up[j][i] = 0;
    h[root] = 0;
    dfs(root, 0);
    // cout << root << el;
    fu(turn, 0, 1) {
        mp.clear();
        reverse(all(adj[root]));
        for (int x : adj[root]) {
            if (del[x]) continue;
            if (dfsSearch(x, len)) return true;
            dfsUpdate(x, len);
        }
    }
    // return false;
    del[root] = true;
    for (int v : adj[root]) {
        if (del[v]) continue;
        if (check(v, len)) return true;;
    }
    return false;
}
 
signed main() {
//    freopen("bai3.inp", "r", stdin);
//    freopen("bai3.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s;
    s = ' ' + s;
    sz = sz(s) - 1;
    pw[0] = 1;
    fu(i, 1, n) pw[i] = pw[i - 1] * base;
    fu(i, 2, n) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // cout << check(1, 2);
    int res = 1;
    int l = 1, r = n / 2;
    while (l <= r) {
        int mid = (r + l) / 2;
        // cout << 2 * mid << el;
        fu(i, 1, n) del[i] = 0;
        if (check(1, 2 * mid)) {
            res = 2 * mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    // cout << res;
    l = 1, r = n / 2;
    while (l <= r) {
        int mid = (l + r) / 2;
        fu(i, 1, n) del[i] = 0;
        if (check(1, 2 * mid + 1)) {
            maximize(res, 2 * mid + 1);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << res;
 
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2140 KB Output is correct
2 Correct 56 ms 2140 KB Output is correct
3 Correct 380 ms 2392 KB Output is correct
4 Correct 519 ms 2136 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2140 KB Output is correct
2 Correct 56 ms 2140 KB Output is correct
3 Correct 380 ms 2392 KB Output is correct
4 Correct 519 ms 2136 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Execution timed out 5071 ms 14800 KB Time limit exceeded
9 Halted 0 ms 0 KB -