Submission #1123343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123343		Neco_arc	Cat Exercise (JOI23_ho_t4)	C++20	54 / 100	187 ms	41916 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define name "Cat Exercise"
#define fi(i, a, b)  for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (2e5 + 7)

using namespace std;

int n;
int a[maxn], p[maxn], f[maxn];
int h[maxn], cha[maxn][18];
vector<int> edges[maxn];

struct DSU {
    int lab[maxn];
    DSU() { memset(lab, -1, sizeof lab); }

    int get_rt(int u) { return lab[u] < 0 ? u : lab[u] = get_rt(lab[u]); }

    void uni(int u, int v) {
        int p = get_rt(u), q = get_rt(v); if(p == q) return;
        lab[p] += lab[q], lab[q] = p;
    }

} Dsu;

void dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) {
        cha[v][0] = u, h[v] = h[u] + 1;
        fi(i, 1, 17) cha[v][i] = cha[cha[v][i - 1]][i - 1];
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    fid(i, 17, 0) if(h[u] - (1 << i) >= h[v]) u = cha[u][i];
    fid(i, 17, 0) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
    return u == v ? u : cha[u][0];
}

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

void solve() {

    cin >> n;
    fi(i, 1, n) cin >> a[i], p[i] = i;
    fi(i, 1, n - 1) {
        int x, y; cin >> x >> y;
        edges[x].push_back(y), edges[y].push_back(x);
    }

    dfs(1, 0);
    sort(p + 1, p + 1 + n, [](int x, int y) { return a[x] < a[y]; });

    fi(i, 1, n) {
        int u = p[i];
        for(int v : edges[u]) if(a[v] < a[u]) {
            int p = Dsu.get_rt(v);
            f[u] = max(f[u], f[p] + dist(u, p));
        }
        for(int v : edges[u]) if(a[v] < a[u]) Dsu.uni(u, v);
    }

    cout << f[p[n]];
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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