Submission #1109884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109884		Sharky	Construction of Highway (JOI18_construction)	C++17	100 / 100	827 ms	41952 KiB

construction

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

#define int long long
const int inf = 1e18;

const int N = 1e5 + 10;
const int LG = 17;

int n, lift[N][LG], dep[N], root[N], sz[N], tin[N], par[N], c[N], fen[N], timer = 0, paint[N];
vector<int> adj[N];
pair<int, int> e[N];

void upd(int idx, int k) {
    for (; idx < N; idx += (idx & -idx)) fen[idx] += k;
}

int query(int idx) {
    int res = 0;
    for (; idx; idx -= (idx & -idx)) res += fen[idx];
    return res;
}

void dfs(int u, int p) {
    sz[u] = 1;
    for (int i = 1; i < LG; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
    for (auto& v : adj[u]) {
        if (v == p) continue;
        lift[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[adj[u][0]]) swap(v, adj[u][0]);
    }
}

void hld(int u, int p) {
    tin[u] = ++timer;
    for (int v : adj[u]) {
        if (v == p) continue;
        root[v] = (v == adj[u][0] ? root[u] : v);
        hld(v, u);
    }
}

struct SegTree {
    int size = 1;
    vector<int> seg, lazy;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 10, -inf);
        lazy.assign(2 * size + 10, -inf);
    }
    void push(int id) {
        if (lazy[id] == -inf) return;
        seg[id] = lazy[id];
        if (id < size) for (int i = 0; i < 2; i++) lazy[id*2+i] = lazy[id];
        lazy[id] = -inf;
    }
    void update(int ql, int qr, int val, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[id] = val;
            push(id);
            return;
        }
        int mid = (l + r) / 2;
        update(ql, qr, val, l, mid, id * 2);
        update(ql, qr, val, mid + 1, r, id * 2 + 1);
    }
    int query(int pos, int l, int r, int id) {
        push(id);
        if (l == r) return seg[id];
        int mid = (l + r) / 2;
        if (pos <= mid) return query(pos, l, mid, id * 2);
        return query(pos, mid + 1, r, id * 2 + 1);
    }
} ST;

void update_path(int x, int y, int val) {
    for (; root[x] != root[y]; y = par[root[y]]) {
        if (dep[root[x]] > dep[root[y]]) swap(x, y);
        // cout << "update " << tin[root[y]] << ' ' << tin[y] << ' ' << val << '\n';
        ST.update(tin[root[y]], tin[y], val, 1, n, 1);
    }
    if (dep[x] > dep[y]) swap(x, y);
    // cout << "update " << tin[x] << ' ' << tin[y] << '\n';
    ST.update(tin[x], tin[y], val, 1, n, 1);
}

int jump(int sta, int dist) {
    for (int i = LG - 1; i >= 0; i--) if (dist & (1 << i)) sta = lift[sta][i];
    return sta;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<int> disc;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        disc.push_back(c[i]);
    }
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());
    for (int i = 1; i <= n; i++) {
        c[i] = lower_bound(disc.begin(), disc.end(), c[i]) - disc.begin() + 1;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        paint[i] = c[v];
        adj[u].push_back(v);
        par[v] = u;
        e[i] = {u, v};
    }
    // for (int i = 1; i < n; i++) cout << paint[i] << '\n';
    lift[1][0] = 1, root[1] = 1;
    dfs(1, -1);
    hld(1, -1);
    ST.init(n + 1);
    for (int i = 1; i < n; i++) {
        int node = e[i].first;
        vector<pair<int, int>> vec;
        int tmp = ST.query(tin[node], 1, n, 1);
        // cout << "yo\n";
        int rt = i-1;
        if (!rt) rt = -inf;
        while (node >= 1) {
            // cout << "node: " << node << '\n';
            if (tmp == rt) {
                vec.push_back({tmp, dep[node] + 1});
                break;
            }
            int l = 1, r = dep[node];
            // find min x s.t. col[x] != 
            while (l < r) {
                int mid = (l + r) / 2;
                int tar = jump(node, mid);
                if (ST.query(tin[tar], 1, n, 1) != tmp) r = mid;
                else l = mid + 1;
            }
            vec.push_back({tmp, l});
            node = jump(node, l);
            tmp = ST.query(tin[node], 1, n, 1);
        }
        reverse(vec.begin(), vec.end());
        int inv = 0, tot = 0;
        if (i > 1) {
            for (auto& [x, y] : vec) {
                // cout << "pair: " << x << " " << y << '\n';
                inv += (tot - query(paint[x])) * y;
                upd(paint[x], y);
                tot += y;
            }
            for (auto& [x, y] : vec) upd(paint[x], -y);
        }
        // cout << "test\n";
        update_path(1, e[i].second, i);
        cout << inv << '\n';
    }
}

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