Submission #362930

#	Time	Username	Problem	Language	Result	Execution time	Memory
362930		dolphingarlic	Construction of Highway (JOI18_construction)	C++14	100 / 100	620 ms	108780 KiB

construction

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

int c[100001], u[100001], v[100001], par[100001];
vector<int> graph[100001];
int heavy[100001], head[100001], depth[100001];
deque<pair<int, int>> hld_vals[100001];

int dfs(int node = 1) {
    int sz = 1, mx = 0;
    for (int i : graph[node]) {
        int csz = dfs(i);
        sz += csz;
        if (csz > mx) mx = csz, heavy[node] = i;
    }
    return sz;
}

void decompose(int node = 1, int h = 1, int d = 1) {
    head[node] = h; depth[node] = d;
    if (heavy[node]) decompose(heavy[node], h, d + 1);
    for (int i : graph[node]) if (i != heavy[node]) decompose(i, i, 1);
}

ll count_inversions(deque<pair<int, int>> &path) {
    map<int, int> comp;
    for (pair<int, int> i : path) comp[i.first];
    int n = 0;
    for (auto &i : comp) i.second = ++n;

    ll ans = 0;
    vector<ll> bit(n + 1);
    for (pair<int, int> i : path) {
        for (int j = comp[i.first] - 1; j; j -= j & -j) ans += bit[j] * i.second;
        for (int j = comp[i.first]; j <= n; j += j & -j) bit[j] += i.second;
    }
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i < n; i++) {
        cin >> u[i] >> v[i];
        graph[u[i]].push_back(v[i]);
        par[v[i]] = u[i];
    }
    dfs(); decompose();

    hld_vals[1].push_back({c[1], 1});
    for (int i = 1; i < n; i++) {
        deque<pair<int, int>> path;
        int curr = v[i];
        while (curr) {
            deque<pair<int, int>> ins;
            int rem = depth[curr] - (curr == v[i]), h = head[curr];
            while (rem) {
                if (hld_vals[h][0].second <= rem) {
                    rem -= hld_vals[h][0].second;
                    ins.push_front(hld_vals[h][0]);
                    hld_vals[h].pop_front();
                } else {
                    ins.push_front({hld_vals[h][0].first, rem});
                    pair<int, int> upd = {hld_vals[h][0].first, hld_vals[h][0].second - rem};
                    hld_vals[h].pop_front();
                    hld_vals[h].push_front(upd);
                    rem = 0;
                }
            }
            hld_vals[h].push_front({c[v[i]], depth[curr]});
            path.insert(path.end(), ins.begin(), ins.end());
            curr = par[h];
        }
        cout << count_inversions(path) << '\n';
    }
    return 0;
}

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