Submission #1285625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285625		khoavn2008	Cat Exercise (JOI23_ho_t4)	C++17	51 / 100	93 ms	45572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 2e5 + 10, INF = 1e9, LOG = 18;
int n,a[N],par[N],ma[N],high[N];
ll s[N];
int tpos,pos[N],MIHIGH[LOG + 1][N];
pair<int,int> edge[N];
vector<int> adj[N];
void dfs(int u,int p = -1){
    pos[u] = ++tpos;
    MIHIGH[0][tpos] = u;
    for(int v : adj[u]){
        if(v == p)continue;
        high[v] = high[u] + 1;
        dfs(v, u);
        MIHIGH[0][++tpos] = u;
    }
}
#define MIN(u, v) (high[u] < high[v] ? u : v)
int LCA(int u,int v){
    if(pos[u] > pos[v])swap(u, v);
    int tmp = __lg(pos[v] - pos[u] + 1);
    return MIN(MIHIGH[tmp][pos[u]], MIHIGH[tmp][pos[v] - MASK(tmp) + 1]);
}
int Dist(int u,int v){return high[u] + high[v] - high[LCA(u, v)] * 2;}
int find(int u){return u == par[u] ? u : par[u] = find(par[u]);}
void merge(int u,int v){
    v = find(v);
    par[v] = u;
    s[u] = max(s[u], s[v] + Dist(u, ma[v]));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    FOR(i,1,n)par[i] = i, ma[i] = i;
    FOR(i,1,n)cin>>a[i];
    FOR(i,1,n - 1){
        int u,v;cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
        if(a[u] < a[v])swap(u, v);
        edge[i] = {u, v};
    }
    dfs(1);
    FOR(j,1,LOG)FOR(i,1,tpos - MASK(j) + 1)MIHIGH[j][i] = MIN(MIHIGH[j - 1][i], MIHIGH[j - 1][i + MASK(j - 1)]);
    sort(edge + 1, edge + n, [&](const pair<int,int> &lhs,const pair<int,int> &rhs)->bool{
        return a[lhs.fi] < a[rhs.fi];
    });
    FOR(i,1,n - 1){
        int u = edge[i].fi, v = edge[i].se;
        merge(u, v);
    }
    ll ans = 0;
    FOR(i,1,n)ans = max(ans, s[i]);
    cout<<ans;
}

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