제출 #131927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131927		imeimi2000	Construction of Highway (JOI18_construction)	C++17	100 / 100	830 ms	19940 KiB

construction

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n;
int C[100001];
int A[100001];
int B[100001];
vector<int> child[100001];
int sz[100001];

int dep[100001];
int par[100001];
void dfs1(int x) {
    sz[x] = 1;
    for (int i : child[x]) {
        dep[i] = dep[x] + 1;
        dfs1(i);
        sz[i] += sz[x];
    }
    sort(child[x].begin(), child[x].end(), [&](int a, int b) {
        return sz[a] > sz[b];
    });
}

int hidx[100001];
int st[100001];
int re[100001];
void dfs2(int x) {
    static int ord = 0;
    if (hidx[x] == 0) hidx[x] = x;
    re[st[x] = ++ord] = x;
    if (child[x].empty()) return;
    hidx[child[x][0]] = hidx[x];
    for (int i : child[x]) {
        dfs2(i);
    }
}

set<pii> sp;
vector<pii> gs;

void hld_up(int x, int c) {
    if (x == 0) return;
    int idx = hidx[x];
    auto it = sp.lower_bound(pii(st[x] + 1, 0));
    if (hidx[re[it->fs]] == idx) {
        gs.emplace_back(it->se, st[x] - max(st[idx] - 1, prev(it)->fs));
    }
    while (1) {
        it = --sp.lower_bound(pii(st[x] + 1, 0));
        if (it->fs < st[idx]) break;
        gs.emplace_back(it->se, it->fs - max(st[idx] - 1, prev(it)->fs));
        sp.erase(it);
    }
    sp.emplace(st[x], c);
    hld_up(par[idx], c);
}

vector<int> cp;
llong fen[100001];

void init(int i) {
    while (i <= 100000) {
        fen[i] = 0;
        i += i & -i;
    }
}

void init() {
    for (int i : cp) init(i);
    cp.clear();
}

void update(int i, int x) {
    cp.push_back(i);
    while (i <= 100000) {
        fen[i] += x;
        i += i & -i;
    }
}

llong query(int i) {
    llong ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

llong get_ans() {
    llong ret = 0;
    init();
    for (pii i : gs) {
        ret += query(i.fs - 1) * i.se;
        update(i.fs, i.se);
    }
    gs.clear();
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> C[i];
        cp.push_back(C[i]);
    }
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for (int i = 1; i <= n; ++i) {
        C[i] = lower_bound(cp.begin(), cp.end(), C[i]) - cp.begin() + 1;
    }
    cp.clear();
    for (int i = 1; i < n; ++i) {
        cin >> A[i] >> B[i];
        par[B[i]] = A[i];
        child[A[i]].push_back(B[i]);
    }
    dfs1(1);
    dfs2(1);
    sp.emplace(0, 0);
    sp.emplace(n + 1, 0);
    sp.emplace(st[1], C[1]);
    for (int i = 1; i < n; ++i) {
        hld_up(B[i], C[B[i]]);
        printf("%lld\n", get_ans());
    }
    return 0;
}

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