제출 #1283844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283844		tuongll	Construction of Highway (JOI18_construction)	C++20	100 / 100	217 ms	22092 KiB

construction

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

template<typename T>
struct Fenwick {
    int n, m = 1;
    vector<T> bit;
    Fenwick(int n): n(n), bit(n + 1){
        while(2 * m <= n) m *= 2;
    }
    void update(int i, T x){
        for (; i <= n; i += i & -i)
            bit[i] += x;
    }
    T get(int i){
        T res = 0;
        for (; i; i -= i & -i)
            res += bit[i];
        return res;
    }
    T get(int l, int r){
        return get(r) - get(l - 1);
    }
    int order(T k){
        T s = 0;
        int pos = 0;
        for (int i = m; i; i >>= 1){
            if (pos + i < n && s + bit[pos + i] < k){
                pos += i;
                s += bit[pos];
            }
        }
        return pos + 1;
    }
};

const int N = 1e5 + 3;

vector<int> g[N];
int dep[N], heavy[N], par[N], head[N];

vector<pair<int, int>> chain[N]; // store in chain[head[u]]

void init(){
    auto dfs = [&](auto &dfs, int u, int pre) -> int {
        int sz = 1, mxsz = 0;
        for (int v : g[u]) if (v != pre){
            par[v] = u;
            dep[v] = dep[u] + 1;

            int csz = dfs(dfs, v, u);
            if (csz > mxsz){
                heavy[u] = v;
                mxsz = csz;
            }
            sz += csz;
        }

        return sz;
    };
    dfs(dfs, 1, 0);

    auto decompose = [&](auto &decompose, int u, int top) -> void {
        head[u] = top;
        if (heavy[u]) decompose(decompose, heavy[u], top);
        for (int v : g[u]) if (v != par[u] && v != heavy[u])
            decompose(decompose, v, v);
    };
    decompose(decompose, 1, 1);
}

// returns path from st -> 1 in compressed form
// also assigns all colors on path to x
vector<pair<int, int>> get(int st, int x){
    vector<pair<int, int>> res, cur;
    for (int u = st; u != 0; u = par[head[u]]){
        int h = dep[u] - dep[head[u]] + 1, tot = 0;

        cur.clear();
        while(!chain[head[u]].empty()){
            auto [col, cnt] = chain[head[u]].back();
            chain[head[u]].pop_back();
            tot += cnt;

            if (tot >= h){
                if (tot > h) chain[head[u]].emplace_back(col, tot - h);
                if (h - (tot - cnt) > 0) cur.emplace_back(col, h - (tot - cnt));
                break;
            }

            cur.emplace_back(col, cnt);
        }

        chain[head[u]].emplace_back(x, h);

        reverse(begin(cur), end(cur));
        for (auto p : cur)
            res.push_back(p);
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    vector<int> a(n + 1), compress;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        compress.push_back(a[i]);
    }

    sort(begin(compress), end(compress));
    compress.erase(unique(begin(compress), end(compress)), end(compress));
    for (int i = 1; i <= n; ++i)
        a[i] = upper_bound(begin(compress), end(compress), a[i]) - begin(compress);

    vector<int> order;
    for (int i = 1, u, v; i < n; ++i){
        cin >> u >> v;
        g[u].push_back(v);
        order.push_back(v);
    }

    init();

    get(1, a[1]);
    Fenwick<long long> bit(compress.size());

    for (int u : order){
        auto seq = get(u, a[u]);
        reverse(begin(seq), end(seq));

        long long res = 0;
        for (auto [col, cnt] : seq){
            res += 1ll * cnt * bit.get(col + 1, compress.size());
            bit.update(col, cnt);
        }

        cout << res << '\n';

        for (auto [col, cnt] : seq){
            bit.update(col, -cnt);
        }
    }
}

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