oj.uz

Submission #924490

# Submission time Handle Problem Language Result Execution time Memory
924490 2024-02-09T05:39:23 Z Whisper Lampice (COCI19_lampice) C++17
110 / 110
 1834 ms 15192 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 5e4 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int numNode;
string s;
vector<int> adj[MAX];

int sz[MAX], del[MAX];

void reSubize(int u, int p){
    sz[u] = 1;
    for (auto&v : adj[u]) if(v ^ p){
        if (!del[v]){
            reSubize(v, u); sz[u] += sz[v];
        }
    }
}
int getCentroid(int u, int p, int siz){
    for (auto&v : adj[u]) if(v ^ p){
        if (!del[v] && 2 * sz[v] > siz) return getCentroid(v, u, siz);
    }
    return u;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

int l = 0; bool found;
int Pow[MAX];
unordered_map<int, bool> f[MAX];

int maxDepth = 1;
char r;
void dfs(int u, int p, int dep, int up, int down, bool ok){
    if (dep > l) return;
    maximize(maxDepth, dep);
    up = (up * Base + (s[u] - 'a' + 1)) % Mod;
    down = (down + (s[u] - 'a' + 1) * Pow[dep - 1]) % Mod;
    int val = ((down * Pow[l - dep] - up) + Mod) % Mod;
    if (ok) f[dep][val] = 1;
    else{
        if (dep + 1 == l){
            if ((down * Base + (r - 'a' + 1)) % Mod == up){
                found = 1; return;
            }
        }
        if (l > dep)
            if (f[l - dep - 1].count(val)){
                found = 1; return;
            }
    }
    for (auto&v : adj[u]) if(v ^ p){
        if (!del[v]){
            dfs(v, u, dep + 1, up, down, ok);
            if (found) return;
        }
    }
}
void decompose(int root){
    reSubize(root, -1);
    int siz = sz[root];
    root = getCentroid(root, -1, siz);
    r = s[root];
    del[root] = 1;
    maxDepth = 1;
    for (auto&v : adj[root]) if(!del[v]){
        dfs(v, root, 1, s[root] - 'a' + 1, 0, 0);
        if (found) return;
        dfs(v, root, 1, s[root] - 'a' + 1, 0, 1);
    }
    for (int i = 0; i <= maxDepth; ++i) f[i].clear();
    for (auto&v : adj[root]) if(!del[v]){
        decompose(v);
        if (found) return;
    }
}

bool check(int _l){
    l = _l; found = false;
    for (int i = 0; i <= l; ++i) f[i].clear();
    for (int i = 1; i <= numNode; ++i) del[i] = 0;
    decompose(1);
    return found;
}
void Whisper(){
    cin >> numNode >> s;
    s = '@' + s;
    for (int i = 1; i < numNode; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    Pow[0] = 1;
    for (int i = 1; i <= numNode; ++i){
        Pow[i] = Pow[i - 1] * Base % Mod;
    }
    int ans = 1;
    for (int i = 0; i < 2; ++i){
        int lo = 0, hi = numNode / 2 + 1;
        while (hi - lo > 1){
            int mid = (lo + hi) >> 1;
            if (check(2 * mid + i)) lo = mid;
            else hi = mid;
        }
        maximize(ans, 2 * lo + i);
    }
    cout << ans;
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 8 ms 5572 KB Output is correct
3 Correct 19 ms 5464 KB Output is correct
4 Correct 19 ms 5468 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 1 ms 5548 KB Output is correct
7 Correct 2 ms 5548 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 13848 KB Output is correct
2 Correct 702 ms 14084 KB Output is correct
3 Correct 529 ms 14416 KB Output is correct
4 Correct 632 ms 14756 KB Output is correct
5 Correct 980 ms 15192 KB Output is correct
6 Correct 157 ms 14404 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1455 ms 10960 KB Output is correct
2 Correct 1834 ms 10576 KB Output is correct
3 Correct 1646 ms 11096 KB Output is correct
4 Correct 1590 ms 10840 KB Output is correct
5 Correct 1231 ms 10112 KB Output is correct
6 Correct 1152 ms 9900 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 8 ms 5572 KB Output is correct
3 Correct 19 ms 5464 KB Output is correct
4 Correct 19 ms 5468 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 1 ms 5548 KB Output is correct
7 Correct 2 ms 5548 KB Output is correct
8 Correct 728 ms 13848 KB Output is correct
9 Correct 702 ms 14084 KB Output is correct
10 Correct 529 ms 14416 KB Output is correct
11 Correct 632 ms 14756 KB Output is correct
12 Correct 980 ms 15192 KB Output is correct
13 Correct 157 ms 14404 KB Output is correct
14 Correct 1455 ms 10960 KB Output is correct
15 Correct 1834 ms 10576 KB Output is correct
16 Correct 1646 ms 11096 KB Output is correct
17 Correct 1590 ms 10840 KB Output is correct
18 Correct 1231 ms 10112 KB Output is correct
19 Correct 1152 ms 9900 KB Output is correct
20 Correct 942 ms 8748 KB Output is correct
21 Correct 1080 ms 9500 KB Output is correct
22 Correct 1594 ms 9828 KB Output is correct
23 Correct 348 ms 8028 KB Output is correct
24 Correct 1276 ms 9676 KB Output is correct
25 Correct 1250 ms 9240 KB Output is correct
26 Correct 1614 ms 11100 KB Output is correct
27 Correct 1623 ms 10080 KB Output is correct
28 Correct 1091 ms 8228 KB Output is correct
29 Correct 1108 ms 8236 KB Output is correct
30 Correct 1230 ms 10524 KB Output is correct
31 Correct 1079 ms 9040 KB Output is correct
32 Correct 1028 ms 11796 KB Output is correct
33 Correct 763 ms 9656 KB Output is correct