Submission #794859

#	Time	Username	Problem	Language	Result	Execution time	Memory
794859		PurpleCrayon	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	2066 ms	34612 KiB

designated_cities

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

int n;
vector<ar<int, 3>> adj[N];
ll ans[N];

ll calc_one(int c, int p) {
    ll sum = 0;
    for (auto [nxt, w, _] : adj[c]) if (nxt != p) {
        sum += w + calc_one(nxt, c);
    }
    return sum;
}

void dfs1(int c, int p, ll x) {
    ans[1] = min(ans[1], x);
    for (auto [nxt, a, b] : adj[c]) if (nxt != p) {
        dfs1(nxt, c, x - a + b);
    }
}

int sub[N];
bool blocked[N];

int dfs_sub(int c, int p) {
    sub[c] = 1;
    for (auto [nxt, x, y] : adj[c]) if (nxt != p && !blocked[nxt]) {
        sub[c] += dfs_sub(nxt, c);
    }

    return sub[c];
}

int dfs_cent(int c, int p, int cnt) {
    for (auto [nxt, x, y] : adj[c]) if (nxt != p && !blocked[nxt] && sub[nxt] > cnt / 2)
        return dfs_cent(nxt, c, cnt);

    return c;
}

pair<ll, int> dfs_best(int c, int p, ll x) {
    pair<ll, int> best{x, c};
    for (auto [nxt, w, _] : adj[c]) if (!blocked[nxt] && nxt != p) {
        best = max(best, dfs_best(nxt, c, x + w));
    }

    return best;
}

vector<int> roots;
int process(int c) {
    roots.push_back(c); // can't hurt, and probably useful

    ll best_w = -1;
    int best_nxt = -1, best_c = -1;

    for (auto [nxt, w, _] : adj[c]) if (!blocked[nxt]) {
        auto cur = dfs_best(nxt, c, w);
        if (cur.first > best_w) {
            best_w = cur.first;
            best_nxt = nxt;
            best_c = cur.second;
        }
    }

    if (best_c != -1) {
        roots.push_back(best_c);
    }
    return best_nxt;
}

void build(int c) {
    if (c == -1) return;
    int cnt = dfs_sub(c, -1);
    int cent = dfs_cent(c, -1, cnt);

    int nxt = process(cent);
    blocked[cent] = 1;
    build(nxt);
}


int par[N], par_w[N], st[N], en[N], et[N], tt;
ll sum[N];
bool marked[N];

ll lzy[4 * N];
pair<ll, int> t[4 * N];

void build(int v, int tl, int tr) {
    if (tl == tr) t[v] = {sum[tl], tl};
    else {
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm), build(2*v+1, tm+1, tr);
        t[v] = max(t[2*v], t[2*v+1]);
    }
}

void push(int v, int tl, int tr, ll x) {
    if (!x) return;
    t[v].first += x;
    if (tl != tr)
        lzy[2*v] += x, lzy[2*v+1] += x;
}

void app(int v, int tl, int tr) {
    push(v, tl, tr, lzy[v]);
    lzy[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, ll x) {
    app(v, tl, tr);
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        push(v, tl, tr, x);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(2*v, tl, tm, l, r, x), upd(2*v+1, tm+1, tr, l, r, x);
    t[v] = max(t[2*v], t[2*v+1]);
}

pair<ll, int> qry(int v, int tl, int tr, int l, int r) {
    app(v, tl, tr);
    if (r < tl || l > tr) return {-INF, -1};
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return max(qry(2*v, tl, tm, l, r), qry(2*v+1, tm+1, tr, l, r));
}


void dfs_root(int c, int p) {
    par[c] = p;
    et[st[c] = tt++] = c;
    for (auto [nxt, w, _] : adj[c]) if (nxt != p) {
        par_w[nxt] = w;
        dfs_root(nxt, c);
    }
    en[c] = tt-1;
}

void add(int root) {
    tt = 0;
    memset(par, -1, sizeof(par));
    memset(sum, 0, sizeof(sum));
    memset(par_w, 0, sizeof(par_w));

    dfs_root(root, -1);
    for (int i = 1; i < n; i++) {
        int c = et[i];
        sum[i] = sum[st[par[c]]] + par_w[c];
    }

    memset(marked, 0, sizeof(marked));
    ll cur = accumulate(par_w, par_w + n, 0LL);
    build(1, 0, n-1);
    for (int i = 1; i <= n; i++) {
        /*
        pair<ll, int> best{-1, -1};
        for (int c = 0; c < n; c++) best = max(best, {sum[c], c});
        */
        pair<ll, int> best = qry(1, 0, n-1, 0, n-1);

        int c = et[best.second];
        while (c != -1 && !marked[c]) {
            marked[c] = 1;
            upd(1, 0, n-1, st[c], en[c],  -par_w[c]);
            // for (int j = st[c]; j <= en[c]; j++) sum[j] -= par_w[c];
            cur -= par_w[c];
            c = par[c];
        }

        ans[i+1] = min(ans[i+1], cur);
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        int x, y; cin >> x >> y;
        adj[a].push_back({b, x, y});
        adj[b].push_back({a, y, x});
    }

    fill(ans, ans + n, INF);
    dfs1(0, -1, calc_one(0, -1));

    build(0);
    for (int c : roots) add(c);

    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << ans[x] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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