Help me optimize my solution for 383 Div1 D pls
Разница между en1 и en2, 263 символ(ов) изменены
Link to the problem:↵
https://codeforces.me/contest/741/problem/D↵

I came up with a solution using Small To Large and Xor Hashing, but my time complexity is $O(n*log^2(n)*26)$, which is still not optimized enough. It got the extra $log$ from using ```map```, and I'm not sure of how to get rid of the ```map```. Can someone help me pls?↵


<spoiler summary="My Code (I switched to unordered_map and it still TLEs)">↵
```c++↵
#include <bits/stdc++.h>↵
using namespace std;↵

//#define int long long //emergency debug↵

typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef pair<ii,int> iii;↵
#define f first↵
#define s second↵
#define pb push_back↵
#define mp make_pair↵
#define hellnah cout<<"NO\n"↵
#define fuckyeah cout<<"YES\n"↵
#define en '\n'↵


const ll oo = 1e9;↵
const ll mod = 1e9+7;↵


int n;↵
vector<ii> g[500005];↵
int b[500005];↵
int hv[500005];↵
int rnk[500005];↵
int dp[500005];↵
int sz[500005];↵



void dfs(int u){↵
    sz[u] = 1;↵
    ii tmp = mp(0,0);↵
    for(ii p : g[u]){↵
        int v = p.f;↵
        int x = p.s;↵
        rnk[v] = rnk[u]+1;↵
        b[v]=b[u]^x;↵
        dfs(v);↵
        sz[u]+=sz[v];↵
        tmp = max(tmp,mp(sz[v],v));↵
    }↵

    hv[u] = tmp.s;↵
}↵

void hld(int u, vector<int> &sub, unordered_map<int,int> &s){↵


    if(hv[u]){↵
        hld(hv[u],sub,s);↵
        dp[u] = dp[hv[u]];↵
        for(int i = 0;i<26;i++){↵
            int x = b[u]^(1<<i);↵
            if(s.find(x)!=s.end())↵
            dp[u] = max(dp[u], s[x]-rnk[u]);↵
        }↵
        if(s.find(b[u])!=s.end())↵
        dp[u] = max(dp[u], s[b[u]]-rnk[u]);↵
    }↵

    s[b[u]] = max(s[b[u]], rnk[u]);↵
    sub.pb(u);↵




    for(ii p : g[u]){↵
        int v = p.f;↵
        if(v==hv[u]) continue;↵

        vector<int> sub2;↵
        unordered_map<int,int> s2;↵
        s2.reserve(sz[v]);↵
        hld(v, sub2, s2);↵
        dp[u] = max(dp[u], dp[v]);↵

        for(int x : sub2){↵
            int k = b[x];↵
            for(int i = 0;i<26;i++){↵
                int tmp = k^(1<<i);↵
                if(s.find(tmp)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[tmp]-rnk[u]*2);↵
            }↵
            if(s.find(k)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[k]-rnk[u]*2);↵

        }↵
        for(int x : sub2){↵
            sub.pb(x);↵
            s[b[x]] = max(s[b[x]], rnk[x]);↵
        }↵
    }↵
}↵


int32_t main(){↵
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵

//    #ifndef ONLINE_JUDGE↵
//        freopen("abc.inp","r",stdin);↵
//        freopen("abc.out","w",stdout);↵
//    #endif↵

    cin>>n;↵
    for(int i = 2;i<=n;i++){↵
        int u; char c;↵
        cin>>u>>c;↵
        int x = (1<<(c-'a'));↵
        g[u].pb(mp(i,x));↵
    }↵


    rnk[1] = 1;↵
    dfs(1);↵


    vector<int> sub;↵
    unordered_map<int,int> s;↵

    s.reserve(n);↵
    hld(1, sub, s);↵
    for(int i = 1;i<=n;i++) cout<<max(dp[i],0)<<' '; cout<<en;↵

    return 0;↵
}↵

```↵
</spoiler>↵



EDIT: Got rid of the ```map```, not sure how to explain it tho. And the solution above would've WAed test 32 because i forgot to make the default value of the map to be ```-INF```↵

Accepted solution: https://codeforces.me/contest/741/submission/287930415↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский PUSSY_LICKING_LOLI_69 2024-10-25 16:48:04 263
en1 Английский PUSSY_LICKING_LOLI_69 2024-10-25 07:51:42 2989 Initial revision (published)