제출 #1278098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278098		dosts	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	314 ms	66168 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;

const int N = 2e5+1;
vi edges[N],tin(N),tout(N),d(N);
int up[N][20];

int timer = 1;
void dfs(int node,int p,int der = 0) {
    d[node] = der;
    tin[node] = timer++;
    up[node][0] = p;
    for (int i=1;i<20;i++) up[node][i] = up[up[node][i-1]][i-1];
    for (auto it : edges[node]) {
        if (it == p) continue;
        dfs(it,node,der+1);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i = 19;i>=0;i--) {
        if (!anc(up[a][i],b)) a = up[a][i];
    }
    return up[a][0];
}

int dist(int a,int b) {
    return d[a]+d[b]-2*d[lca(a,b)];
}

struct DSU {
    vi dad;

    DSU(int nn) {
        dad.resize(nn+1);
        iota(all(dad),0ll);
    }

    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }

    void unite(int x,int y) {
        dad[find(x)] = find(y);
    }
};

void solve() {
    int n;
    cin >> n;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n-1;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1,1);
    DSU dsu(n);
    vi ord(n+1);
    iota(all(ord),0ll);
    sort(1+all(ord),[&](int x,int y) {
        return a[x] < a[y]; 
    });

    vi dp(n+1,0);
    for (int i=1;i<=n;i++) {
        int node = ord[i];
        int mx = 0;
        for (auto it : edges[node]) {
            if (a[it] > a[node]) continue;
            //cout << node sp dsu.find(it) sp dist(dsu.find(it),node) << '\n';
            mx = max(mx,dist(dsu.find(it),node)+dp[dsu.find(it)]);
        }
        dp[node] = mx;
        for (auto it : edges[node]) {
            if (a[it] > a[node]) continue;
            dsu.unite(it,node);
        }
    }
    cout << dp[ord[n]] << '\n'; 
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• 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