Submission #47517

#	Time	Username	Problem	Language	Result	Execution time	Memory
47517		qoo2p5	Construction of Highway (JOI18_construction)	C++17	100 / 100	372 ms	22216 KiB

construction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 1e5 + 123;

struct F {
    int f[N];
    
    void add(int x, int y) {
        x++;
        for (; x < N; x += x & (-x)) f[x] += y;
    }
    
    int get(int i) {
        i++;
        int res = 0;
        for (; i > 0; i -= i & (-i)) res += f[i];
        return res;
    }
};

int n;
int c[N];
map<int, int> comp;
vector<int> g[N];

struct HLD {
    int up, down;
    vector<pair<int, int>> st;
    
    void set(int len, int c) {
        int alr = 0;
        while (sz(st) && st.back().second + alr <= len) {
            alr += st.back().second;
            st.pop_back();
        }
        assert(alr <= len);
        if (alr < len) {
            st.back().second -= (len - alr);
        }
        st.pb({c, len});
    }
};

int ptr;
HLD hld[N];
int id[N];
int depth[N];
int cnt[N];
int p[N];
pair<int, int> q[N];

void precalc(int v) {
    cnt[v] = 1;
    for (int u : g[v]) {
        precalc(u);
        cnt[v] += cnt[u];
    }
}

void build_hld(int v, int cur = -1) {
    if (cur == -1) {
        cur = ptr++;
        hld[cur].up = v;
    }
    id[v] = cur;
    hld[cur].down = v;
    int to = -1;
    for (int u : g[v]) {
        if (to == -1 || cnt[u] > cnt[to]) {
            to = u;
        }
    }
    if (to != -1) {
        build_hld(to, cur);
    }
    for (int u : g[v]) {
        if (u != to) {
            build_hld(u, -1);
        }
    }
}

F f;

ll get(int v) {
    static vector<pair<int, int>> cool;
    cool.clear();
    while (v > 0) {
        int w = id[v];
        int len = depth[v] - depth[hld[w].up] + 1;
        int alr = 0;
        int ptr = sz(hld[w].st) - 1;
        while (ptr >= 0 && hld[w].st[ptr].second + alr <= len) {
            alr += hld[w].st[ptr].second;
            ptr--;
        }
        if (alr < len) {
            assert(ptr >= 0);
            cool.pb({hld[w].st[ptr].first, len - alr});
        }
        rep(i, ptr + 1, sz(hld[w].st)) {
            cool.pb(hld[w].st[i]);
        }
        v = p[hld[w].up];
    }
    
    ll ans = 0;
    for (auto &it : cool) {
        ans += it.second * f.get(it.first - 1);
        f.add(it.first, it.second);
    }
    for (auto &it : cool) {
        f.add(it.first, -it.second);
    }
    
    return ans;
}

void set_color(int v, int c) {
    while (v > 0) {
        int w = id[v];
        int len = depth[v] - depth[hld[w].up] + 1;
        hld[w].set(len, c);
        v = p[hld[w].up];
    }
}

void run() {
    cin >> n;
    rep(i, 1, n + 1) {
        cin >> c[i];
        comp[c[i]] = 1;
    }
    {
        int ptr = 0;
        for (auto &it : comp) {
            it.second = ptr++;
        }
    }
    rep(i, 1, n + 1) {
        c[i] = comp[c[i]];
    }
    rep(i, 1, n) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        p[b] = a;
        depth[b] = depth[a] + 1;
        q[i] = {a, b};
    }
    precalc(1);
    build_hld(1);
    rep(i, 0, ptr) {
        hld[i].st.pb({-1, depth[hld[i].down] - depth[hld[i].up] + 1});
    }
    
    set_color(1, c[1]);
    rep(i, 1, n) {
        cout << get(q[i].first) << "\n";
        set_color(q[i].second, c[q[i].second]);
    }
}

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