Submission #797883

#	Time	Username	Problem	Language	Result	Execution time	Memory
797883		vjudge1	Construction of Highway (JOI18_construction)	C++17	100 / 100	256 ms	21708 KiB

construction

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 100100;
const int mod = 1e9 + 7;

using namespace std;

int n;
int a[N];
int A[N], B[N];
int s[N];
int st[N];
int dip[N];
int par[N];
vector<int> v[N];
vector<pair<int, int>> d[N];

void dfs(int x)
{
    if (!st[x]) {
        st[x] = x;
    }

    int big = -1;
    for (int y: v[x]) {
        if (big == -1 || s[y] > s[big]) {
            big = y;
        }
    }
    if (big != -1) {
        st[big] = st[x];
    }
    for (int y: v[x]) {
        dfs(y);
    }

    d[st[x]].push_back({a[x], 1});
}

vector<pair<int, int>> ex(int x, int k, int c)
{
    int initial_k = k;
    vector<pair<int, int>> res;
    while (k > 0) {
        int g = min(k, d[x].back().se);
        d[x].back().se -= g;
        k -= g;
        res.push_back({d[x].back().fi, g});
        if (!d[x].back().se) {
            d[x].pop_back();
        }
    }
    d[x].push_back({c, initial_k});
    reverse(res.begin(), res.end());
    return res;
}

int t[N];

void upd(int x, int g)
{
    while (x < N) {
        t[x] += g;
        x += x & -x;
    }
}

int get(int x)
{
    int res = 0;
    while (x > 0) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

long long inversions(const vector<pair<int, int>>& v)
{
    long long res = 0;
    for (const auto& p : v) {
        res += 1ll * get(p.fi - 1) * p.se;
        upd(p.fi, p.se);
    }
    for (const auto& p : v) {
        upd(p.fi, -p.se);
    }
    return res;
}

long long solve(int A, int c)
{
    vector<pair<int, int>> v;
    while (A > 0) {
        auto g = ex(st[A], dip[A] - dip[st[A]] + 1, c);
        v.insert(v.end(), g.begin(), g.end());
        A = par[st[A]];
    }
    return inversions(v);
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    cin >> n;
    vector<pair<int, int>> ord;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ord.push_back({a[i], i});
        s[i] = 1;
    }
    sort(ord.begin(), ord.end());
    for (int i = 0, j = 1; i < n; i++) {
        if (i > 0 && ord[i].fi > ord[i - 1].fi) {
            j++;
        }
        a[ord[i].se] = j;
    }

    for (int i = 1; i < n; i++) {
        cin >> A[i] >> B[i];

        par[B[i]] = A[i];
        dip[B[i]] = dip[A[i]] + 1;

        v[A[i]].push_back(B[i]);
    }
    for (int i = n - 1; i >= 1; i--) {
        s[A[i]] += s[B[i]];
    }

    dfs(1);
    for (int i = 1; i < n; i++) {
        cout << solve(A[i], a[B[i]]) << "\n";
    }
}

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