oj.uz

Submission #1037118

# Submission time Handle Problem Language Result Execution time Memory
1037118 2024-07-28T07:21:12 Z TrinhKhanhDung Lampice (COCI19_lampice) C++14
110 / 110
 3120 ms 12772 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 5e4 + 10;
const int base = 311;

int N;
string s;
vector<int> adj[MAX];
int nChild[MAX], pw[MAX], height[MAX];
bool ok[MAX];
int ans = 0;
bool isDel[MAX];

void input(){
    cin >> N;
    cin >> s;
    s = "0" + s;
    for(int i=1; i<N; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    pw[0] = 1;
    for(int i=1; i<=N; i++){
        pw[i] = 1LL * pw[i - 1] * base % MOD;
    }
}

namespace subtask1{
    void dfs(int u, int p, int down, int up, int height){
        down = (1LL * down * base + s[u]) % MOD;
        up = (1LL * up + 1LL * s[u] * pw[height] % MOD) % MOD;
        if(down == up) maximize(ans, height + 1);

        for(int v: adj[u]) if(v != p){
            dfs(v, u, down, up, height + 1);
        }
    }

    void solve(){
        pw[0] = 1;
        for(int i=1; i<=N; i++){
            pw[i] = 1LL * pw[i - 1] * base % MOD;
        }

        for(int i=1; i<=N; i++){
            dfs(i, 0, 0, 0, 0);
        }
        cout << ans << '\n';
    }
}

void countChild(int u, int p){
    nChild[u] = 1;
    for(int v: adj[u]) if(v != p && !isDel[v]){
        countChild(v, u);
        nChild[u] += nChild[v];
    }
}

int centroid(int u, int p, int n){
    for(int v: adj[u]) if(v != p && !isDel[v]){
        if(nChild[v] * 2 > n) return centroid(v, u, n);
    }
    return u;
}

bool calc(int u, int p, int h, int down, int up, int len, unordered_map<int, int> &om){
    h++;
    down = (1LL * down * base + s[u]) % MOD;
    up = (1LL * up + 1LL * s[u] * pw[h] % MOD) % MOD;

    if(h + 1 > len) return false;
//    cout << u << ' ' << h << ' ' << down << ' ' << up << '\n';
    height[h + 1] = down;

    if((h + 1) * 2 >= len){
        int par = 2 * (h + 1) - len;
        if(ok[par] && om.count((height[h + 1] - 1LL * height[par] * pw[h + 1 - par] % MOD + MOD * MOD) % MOD)){
            return true;
        }
    }

    if(down == up) ok[h + 1] = true;
    bool ans = false;
    for(int v: adj[u]) if(v != p && !isDel[v]){
        ans = ans || calc(v, u, h, down, up, len, om);
    }

    ok[h + 1] = false;

    return ans;
}

void update(int u, int p, int h, int down, int up, int len, unordered_map<int, int> &om){
    h++;
    down = (1LL * down * base + s[u]) % MOD;
    up = (1LL * up + 1LL * s[u] * pw[h] % MOD) % MOD;
    if(h + 1 > len) return;

    om[down] = true;
    for(int v: adj[u]) if(v != p && !isDel[v]){
        update(v, u, h, down, up, len, om);
    }
}

bool solve(int a, int len){
    countChild(a, 0);
    int u = centroid(a, 0, nChild[a]);
//    cout << u << '\n';

    unordered_map<int, int> om;
    om[s[u]] = true;

    for(int v: adj[u]) if(!isDel[v]){
        ok[0] = true;
        height[0] = 0;
        if(calc(v, u, -1, 0, 0, len, om)) return true;
        update(v, u, 0, s[u], s[u], len, om);
    }

    om.clear();
    reverse(ALL(adj[u]));
    for(int v: adj[u]) if(!isDel[v]){
        ok[0] = ok[1] = true;
        height[0] = 0;
        height[1] = s[u];
        if(calc(v, u, 0, s[u], s[u], len, om)) return true;
        update(v, u, -1, 0, 0, len, om);
    }

    isDel[u] = true;
    for(int v: adj[u]) if(!isDel[v]){
        if(solve(v, len)) return true;
    }

    return false;
}

bool check(int k){
    if(k == 0 || k == 1) return true;

    memset(isDel, false, (N + 3) * sizeof(bool));
    return solve(1, k);
}

int odd(){
    int l = 0, r = N - N / 2;

    while(l < r){
        int m = (l + r) >> 1;
        if((l + r) & 1) m++;
        if(check(m * 2 + 1)){
            l = m;
        }
        else{
            r = m - 1;
        }
    }

    return l * 2 + 1;
}

int even(){
    int l = 0, r = N - N / 2;

    while(l < r){
        int m = (l + r) >> 1;
        if((l + r) & 1) m++;
        if(check(m * 2)){
            l = m;
        }
        else{
            r = m - 1;
        }
    }
    return l * 2;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    input();

    cout << max(odd(), even());

    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1628 KB Output is correct
2 Correct 9 ms 1628 KB Output is correct
3 Correct 31 ms 1840 KB Output is correct
4 Correct 29 ms 1628 KB Output is correct
5 Correct 1 ms 1632 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1429 ms 11452 KB Output is correct
2 Correct 1513 ms 11628 KB Output is correct
3 Correct 1084 ms 11852 KB Output is correct
4 Correct 1108 ms 12216 KB Output is correct
5 Correct 1681 ms 12772 KB Output is correct
6 Correct 201 ms 10496 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2575 ms 8956 KB Output is correct
2 Correct 3120 ms 8648 KB Output is correct
3 Correct 2610 ms 9396 KB Output is correct
4 Correct 2479 ms 7856 KB Output is correct
5 Correct 2144 ms 8028 KB Output is correct
6 Correct 1951 ms 7256 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1628 KB Output is correct
2 Correct 9 ms 1628 KB Output is correct
3 Correct 31 ms 1840 KB Output is correct
4 Correct 29 ms 1628 KB Output is correct
5 Correct 1 ms 1632 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1429 ms 11452 KB Output is correct
9 Correct 1513 ms 11628 KB Output is correct
10 Correct 1084 ms 11852 KB Output is correct
11 Correct 1108 ms 12216 KB Output is correct
12 Correct 1681 ms 12772 KB Output is correct
13 Correct 201 ms 10496 KB Output is correct
14 Correct 2575 ms 8956 KB Output is correct
15 Correct 3120 ms 8648 KB Output is correct
16 Correct 2610 ms 9396 KB Output is correct
17 Correct 2479 ms 7856 KB Output is correct
18 Correct 2144 ms 8028 KB Output is correct
19 Correct 1951 ms 7256 KB Output is correct
20 Correct 1400 ms 5320 KB Output is correct
21 Correct 1669 ms 6648 KB Output is correct
22 Correct 2398 ms 8132 KB Output is correct
23 Correct 520 ms 4188 KB Output is correct
24 Correct 2174 ms 6816 KB Output is correct
25 Correct 1863 ms 5956 KB Output is correct
26 Correct 2735 ms 8856 KB Output is correct
27 Correct 2573 ms 8548 KB Output is correct
28 Correct 1628 ms 4444 KB Output is correct
29 Correct 1622 ms 4700 KB Output is correct
30 Correct 2001 ms 7076 KB Output is correct
31 Correct 1785 ms 5724 KB Output is correct
32 Correct 2039 ms 8536 KB Output is correct
33 Correct 1186 ms 6600 KB Output is correct