제출 #1257704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257704		shafi_root	Construction of Highway (JOI18_construction)	C++20	16 / 100	2093 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];
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(vector<pii> vec) {
    ll inv = 0;
    for (int i = 0; i < vec.size(); i++) {
        for (int j = i+1; j < vec.size(); j++) {
            if (vec[i].F < vec[j].F) inv += 1ll * vec[j].S * vec[i].S;
        }
    }
    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]}};
        cout << M_sort(vec) << '\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: 0 / 84