Submission #1107009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107009		_callmelucian	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	163 ms	45644 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
int up[mn][19], depth[mn], p[mn];
vector<int> adj[mn];
bool added[mn];

void dfs (int u, int p, int d) {
    up[u][0] = p, depth[u] = d;
    for (int i = 1; i < 19; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : adj[u])
        if (v != p) dfs(v, u, d + 1);
}

int goUp (int a, int k) {
    for (int i = 0; i < 19; i++)
        if (k & (1 << i)) a = up[a][i];
    return a;
}

int lca (int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = goUp(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int i = 18; i >= 0; i--)
        if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    return up[a][0];
}

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

struct DSU {
    vector<ll> lab, weight, hi;
    DSU (int sz) : lab(sz + 1, -1), weight(sz + 1), hi(sz + 1) {
        for (int i = 1; i <= sz; i++) hi[i] = i;
    }

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    void unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;
        if (-lab[a] < -lab[b]) swap(a, b), weight[a] += distance(hi[a], hi[b]);
        else weight[b] += distance(hi[a], hi[b]);
        lab[a] += lab[b], lab[b] = a;
        weight[a] = max(weight[a], weight[b]);
        hi[a] = max(hi[a], hi[b]);
    }

    ll getWeight (int u) { return weight[get(u)]; }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[p[a]].push_back(p[b]);
        adj[p[b]].push_back(p[a]);
        //cout << p[a] << " " << p[b] << "\n";
    }
    dfs(1, 1, 0);

    DSU dsu(n);
    for (int i = 1; i <= n; i++) {
        for (int j : adj[i])
            if (j < i) dsu.unite(i, j);
    }
    cout << dsu.getWeight(1);

    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