Submission #1257712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257712		shafi_root	Construction of Highway (JOI18_construction)	C++20	100 / 100	266 ms	23740 KiB

construction

/* _In The Name Of God_ */

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

#define maxs(a, b)			a = max(a, b)
#define mins(a, b)			a = min(a, b)
#define pb						push_back
#define F						first
#define S						second
#define lc						id << 1
#define rc						lc|1
#define mid						((l + r)/2)
// #define int                     long long

typedef pair<int, int>     	pii;
typedef long long               	ll;

const ll  MOD    = 1e9  + 7; // 998244353;
const ll  INF    = 1e9  + 1;
const int MXN    = 2e5  + 5;
const int LOG    = 23;

ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }

int n, h[MXN], hd[MXN], sz[MXN], val[MXN], par[MXN];
vector<pii> E, stk[MXN], V;
vector<int> adj[MXN];

void pre_dfs(int v, int p) {
    sz[v] = 1;
    int i = -1;
    h[v] = h[p] + (v != p);
    for (int k = 0; k < adj[v].size(); k++) {
        int u = adj[v][k];
        if (u != p) {
            pre_dfs(u, v); sz[v] += sz[u];
            if (i==-1 || sz[adj[v][i]] < sz[u]) i = k;
        }
    }
    if (i != -1) swap(adj[v][0], adj[v][i]);
}

void hld_dfs(int v, int p) {
    par[v] = p;
    if (adj[v][0] != p) {
        hd[adj[v][0]] = hd[v];
        hld_dfs(adj[v][0], v);
    }
    for (int k = 1; k < adj[v].size(); k++) {
        int u = adj[v][k];
        if (u != p) {
            hd[u] = u;
            hld_dfs(u, v);
        }
    }
}

ll M_sort(int l, int r) {
    if (r - l < 2) return 0;
    ll inv = M_sort(l, mid) + M_sort(mid, r);
    vector<pii> vec;
    int p1 = l, p2 = mid;
    ll sum = 0;
    while (p1 < mid || p2 < r) {
        if (p1 == mid) {
            inv += sum * V[p2].S;
            vec.pb(V[p2++]);
        }
        else if (p2 == r) {
            vec.pb(V[p1++]);
        }
        else {
            if (V[p2].F <= V[p1].F) {
                inv += sum * V[p2].S;
                vec.pb(V[p2++]);
            }
            else {
                sum += V[p1].S;
                vec.pb(V[p1++]);
            }
        }
    }
    for (int i = 0; i < vec.size(); i++) V[l+i] = vec[i];
    vec.clear();
    return inv;
}

void _solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        E.pb({u, v});
    }
    pre_dfs(1, 1);
    hd[1] = 1;
    hld_dfs(1, 1);
    stk[1].pb({h[1], val[1]});
    for (int i = 0; i < n-1; i++) {
        vector<pii> vec;
        int v = E[i].S;
        while (v != 1) {
            vector<pii> cev;
            v = par[v];
            int R = hd[v], bf = h[R]-1;
            while (stk[R].size() && stk[R].back().F <= h[v]) {
                cev.pb({stk[R].back().S, stk[R].back().F-bf});
                bf = stk[R].back().F;
                stk[R].pop_back();
            }
            if (stk[R].size() && bf < h[v]) {
                cev.pb({stk[R].back().S, h[v]-bf});
            }
            stk[R].pb({h[v], val[E[i].S]});
            v = R;
            for (int i = (int)cev.size()-1; i >= 0; i--) {
                vec.pb(cev[i]);
            }
        }
        stk[hd[E[i].S]] = {{h[E[i].S], val[E[i].S]}};
        swap(V, vec);
        cout << M_sort(0, V.size()) << '\n';
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--) _solve();
    return 0.0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84