제출 #1283739

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

construction

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

#define int long long
const int maxn = 1e5 + 5;
int sz[maxn], son[maxn], h[maxn], par[maxn], head[maxn], bit[maxn];
vector<pair<int, int>> s[maxn];
vector<int> g[maxn];

void dfs(int u, int pre){
    sz[u] = 1;
    h[u] = h[pre] + 1;
    par[u] = pre;
    for(int v: g[u]){
        if(v == pre) continue;
        dfs(v, u);
        if(sz[v] > sz[son[u]]) son[u] = v;
        sz[u] += sz[v];
    }
}

void hld(int u, int pre){
    head[u] = pre;
    if(son[u]) hld(son[u], pre);
    for(int v: g[u]){
        if(v == par[u] || v == son[u]) continue;
        hld(v, v);
    }
}
void update(int u, int val){
    while(u){
        int top = head[u];
        int d = h[u] - h[top] + 1;

        while(s[top].size() && s[top].back().first <= d) s[top].pop_back();
        s[top].push_back({d, val});
        u = par[top];
    }
}

void incr(int p, int val){
    for(; p < maxn; p += p & -p) bit[p] += val;
}
int get(int p){
    int res = 0;
    for(; p; p -= p & -p) res += bit[p];
    return res;
}
int query(int u){
    vector<pair<int, int>> ans; 
    while(u){
        int top = head[u];
        int d = h[u] - h[top] + 1;

        vector<pair<int, int>> res;
        int last = 0;
        for(int i = s[top].size() - 1; i >= 0; i--){ 
            auto [x, y] = s[top][i]; 
            res.push_back({min(d, x) - last, y}); 
            last = x; 
            if(x >= d) break; 
        } 

        for(int i = res.size() - 1; i >= 0; i--) ans.push_back(res[i]);
        u = par[top];
    }
    int kq = 0;
    for(auto [x, y]: ans){
        kq += get(y - 1) * x;
        incr(y, x);
    }
    for(auto [x, y]: ans) incr(y, -x);
    return kq;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;

    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int> compress;
    for(int i = 1; i <= n; i++) compress.push_back(a[i]);
    sort(compress.begin(), compress.end());
    
    for(int i = 1; i <= n; i++) a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin() + 1;

    vector<pair<int, int>> edge;
    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge.push_back({u, v});
    }
    
    dfs(1, 0);
    hld(1, 1);
    s[1].push_back({1, a[1]});

    for(auto [u, v]: edge){ 
        cout << query(u) << "\n";
        update(v, a[v]);
    }
}

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