Submission #1191470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191470		Sharky	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	744 ms	94124 KiB

designated_cities

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

#define int long long
const int N = 2e5 + 5;
const int inf = 1e18;

int n, sum = 0, d1 = 0, ans[N], cov[N], sub[N], ps[N], dep[N], tin[N], sz[N], timer = 0, lc = 0, ew[N];
pair<int, int> dp1[N], dp2[N];
array<int, 3> bst = {inf, 0, 0};
vector<array<int, 3>> adj[N];
map<pair<int, int>, int> mp;

void reroot(int u, int v) {
    d1 -= mp[{u, v}];
    d1 += mp[{v, u}];
}

void update(int w, int u, int v) {
    if (w <= bst[0]) bst = {w, u, v};
}

void dfs0(int u, int p) {
    for (auto& [v, w, oth] : adj[u]) {
        if (v == p) continue;
        d1 += w;
        dfs0(v, u);
    }
}

void dfs1(int u, int p) {
    tin[u] = ++timer;
    sz[u] = 1;
    ans[1] = min(ans[1], d1);
    for (auto& [v, w, oth] : adj[u]) {
        if (v == p) continue;
        reroot(u, v);
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        reroot(v, u);
    }
}

void dfsp2(int u, int p) {
    for (auto& [v, w, oth] : adj[u]) {
        if (v == p) continue;
        ps[v] = ps[u] + oth;
        dfsp2(v, u);
        sub[u] += sub[v] + w;
    }
}

void dfs2(int u, int p) {
    dp1[u] = {sub[u], u};
    vector<pair<int, int>> vec;
    for (auto& [v, w, oth] : adj[u]) {
        if (v == p) continue;
        dfs2(v, u);
        dp1[u] = min(dp1[u], pair<int, int> {dp1[v].first + sub[u] - sub[v], dp1[v].second});
        vec.push_back({dp1[v].first - sub[v] - w, dp1[v].second});
    }
    sort(vec.begin(), vec.end());
    if (u == 1) update(vec[0].first + sub[u], 1, vec[0].second);
    if (vec.size() >= 2) {
        // cout << vec[0].first + vec[1].first + sub[u] + ps[u] << " " << vec[0].second << " " << vec[1].second << '\n';
        update(vec[0].first + vec[1].first + sub[u] + ps[u], vec[0].second, vec[1].second);
    }
}

int leaf[N], par[N];

void dfs(int u, int p) {
    int children = 0;
    for (auto& [v, w, oth] : adj[u]) {
        if (v == p) continue;
        par[v] = u;
        ew[v] = w;
        children++;
        ps[v] = ps[u] + w;
        dfs(v, u);
    }
    if (!children) leaf[u] = 1, lc++;
}

struct SegTree {
    int size = 1;
    vector<pair<int, int>> seg;
    vector<int> lazy;
    void init(int sz) {
        while (size < sz) size *= 2;
        seg.assign(2 * size + 10, {0, 0});
        lazy.assign(2 * size + 10, 0);
    }
    void push(int id) {
        seg[id].first += lazy[id];
        if (id < size) {
            for (int i = 0; i < 2; i++) lazy[id * 2 + i] += lazy[id];
        }
        lazy[id] = 0;
    }
    void pull(int id) {
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    void build(int l, int r, int id) {
        if (l == r) {
            if (leaf[l]) seg[id] = {ps[l], l};
            else seg[id] = {-inf, l};
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, id * 2);
        build(mid + 1, r, id * 2 + 1);
        pull(id);
    }
    void update(int ql, int qr, int v, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[id] += v;
            push(id);
            return;
        }
        int mid = (l + r) / 2;
        update(ql, qr, v, l, mid, id * 2);
        update(ql, qr, v, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    pair<int, int> query(int ql, int qr, int l, int r, int id) {
        push(id);
        if (ql <= l && r <= qr) return seg[id];
        if (qr < l || r < ql) return {-inf, 0};
        int mid = (l + r) / 2;
        return max(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
    }
} ST;

void paint(int x) {
    while (x) {
        if (cov[x]) break;
        cov[x] = 1;
        ST.update(tin[x], tin[x] + sz[x] - 1, -ew[x], 1, n, 1);
        x = par[x];
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        adj[u].push_back({v, c, d});
        adj[v].push_back({u, d, c});
        mp[{u, v}] = c, mp[{v, u}] = d;
        sum += c + d;
    }
    dfsp2(1, -1);
    dfs2(1, -1);
    int s = bst[1], t = bst[2];
    ans[2] = bst[0];
    // cout << bst[0] << " " << bst[1] << " " << bst[2] << '\n';
    dfs0(s, -1);
    ans[1] = d1;
    dfs1(s, -1);
    ps[s] = 0;
    dfs(s, -1);
    ST.init(n+1);
    ST.build(1, n, 1);
    paint(t);
    for (int i = 3; i <= lc + 1; i++) {
        pair<int, int> p = ST.query(1, n, 1, n, 1);
        ans[i] = ans[i - 1] + p.first;
        paint(p.second);
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        if (x <= 2) cout << ans[x] << '\n';
        else cout << sum - ans[min(x, lc + 1)] << '\n';
    }
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44