Submission #1082039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082039		Tymond	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	126 ms	41728 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 2e5 + 7;
const int MAXK = 20;
vi g[MAXN];
int a[MAXN];
ll dp[MAXN];
int pos[MAXN];
int dep[MAXN];
int jump[MAXK][MAXN];
bool ok[MAXN];
int rep[MAXN];
int info[MAXN];
int n;
vi akt;

int Find(int x){
    if(x == rep[x]){
        return x;
    }
    return rep[x] = Find(rep[x]);
}

void dfs(int v, int p, int d){
    dep[v] = d;
    jump[0][v] = p;
    for(auto u : g[v]){
        if(u != p){
            dfs(u, v, d + 1);
        }
    }
}

void preprocessing(){
    dfs(1, 1, 0);
    for(int i = 1; i < MAXK; i++){
        for(int j = 1; j <= n; j++){
            jump[i][j] = jump[i - 1][jump[i - 1][j]];
        }
    }
}

int lca(int u, int v){
    if(dep[u] > dep[v]){
        swap(u, v);
    }

    for(int i = MAXK - 1; i >= 0; i--){
        if(dep[v] - dep[u] >= (1 << i)){
            v = jump[i][v];
        }
    }

    if(u == v){
        return v;
    }

    for(int i = MAXK - 1; i >= 0; i--){
        if(jump[i][u] != jump[i][v]){
            u = jump[i][u];
            v = jump[i][v];
        }
    }

    return jump[0][v];
}

int dist(int u, int v){
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void getBest(int v){
    for(auto u : g[v]){
        if(!ok[u]){
            continue;
        }

        int r = Find(u);
        akt.pb(pos[info[r]]);
        int our = Find(v);
        rep[r] = our;
        info[our] = max(info[our], info[r]);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pos[a[i]] = i;
        rep[i] = i;
        info[i] = a[i];
    }

    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    preprocessing();
    for(int i = 1; i <= n; i++){
        akt.clear();
        ok[pos[i]] = 1;
        getBest(pos[i]);

        //cout << i << ' ' << pos[i] << '\n';
        for(auto ele : akt){
            //cout << ele << '\n';
            dp[pos[i]] = max(dp[pos[i]], (ll)dp[ele] + dist(pos[i], ele));
        }
    }

    cout << dp[pos[n]] << '\n';

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26