Submission #46593

#	Time	Username	Problem	Language	Result	Execution time	Memory
46593		nickyrio	Construction of Highway (JOI18_construction)	C++17	100 / 100	570 ms	152164 KiB

construction

//https://oj.uz/problem/view/JOI18_construction
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 100100
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

int n, u[N], v[N], p[N], d[N], c[N], nChild[N], head[N];
vector<int> e[N];

void dfs(int u) {
    nChild[u] = 1;
    for (int v : e[u]) {
        p[v] = u;
        d[v] = d[u] + 1;
        dfs(v);
        nChild[u] += nChild[v];
    }
}

void hld(int u) {
    if (head[u] == 0) head[u] = u;
    int mx = 0, special = -1;
    for (int v : e[u]) {
        if (mx < nChild[v]) {
            special = v; mx = nChild[v];
        }
    }
    for (int v : e[u]) {
        if (v == special) head[v] = head[u];
        else head[v] = v;
        hld(v);
    }
}

long long BIT[N];
long long GetBIT(int u) {
    long long ans = 0;
    for (; u > 0; u -= u & -u) ans += BIT[u];
    return ans;
}

void UpBIT(int u, long long val) {
    for (; u <= n; u += u & -u) BIT[u] += val;
}

struct Data {
    int depth, val, cnt;
};
deque<Data> deq[N];
long long Query(int u) {
    long long ans = 0;
    vector<pp> history;

    while (u) {
        int id = head[u];
        vector<Data> temp;
        int depth = d[u];
        while (!deq[id].empty() && deq[id].back().depth < depth) {
            temp.push_back(deq[id].back());
            deq[id].pop_back();
        }
        if (!deq[id].empty()) {
            Data t = deq[id].back(); deq[id].pop_back();
            int newCnt = t.depth - depth;
            t.cnt -= newCnt;
            temp.push_back(t);
            t.cnt = newCnt;
            if (t.cnt) deq[id].push_back(t);
        }
        while (!temp.empty()) {
            Data t = temp.back(); temp.pop_back();
            ans += 1ll * t.cnt * GetBIT(t.val - 1);
            UpBIT(t.val, t.cnt);
            history.push_back(pp(t.val, t.cnt));
        }
        u = p[head[u]];
    }
    for (pp x : history) UpBIT(x.first, -x.second);
    return ans;
}

void Update(int u) {
    Data x;
    x.val = c[u];
    while (u) {
        int id = head[u];
        x.depth = d[u];
        x.cnt = d[u] - d[p[head[u]]];
       // DEBUG(deq[id].size());
        deq[id].push_back(x);
        u = p[head[u]];
    }
}

int ranking[N];

int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    cin >> n;
    FOR(i, 1, n) cin >> c[i];
    FOR(i, 1, n) ranking[i] = c[i];
    sort(ranking + 1, ranking + n + 1);
    FOR(i, 1, n) {
        c[i] = lower_bound(ranking + 1, ranking + n + 1, c[i]) - ranking;
    }
    FOR(i, 2, n) {
        cin >> u[i] >> v[i];
        e[u[i]].push_back(v[i]);
    }
    d[1] = 1;
    dfs(1);
    hld(1);
    FOR(i, 2, n) {
        cout << Query(u[i]) << '\n';
        Update(v[i]);
    }
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

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