Submission #1127302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127302		OI_Account	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	763 ms	52760 KiB

designated_cities

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

typedef long long ll;

const int N = 200'000;
const ll INF = 1'000'000'000'000'000'000;

int n, q, a[N + 10], b[N + 10];
ll c[N + 10], d[N + 10], w[N + 10];
int mark[N + 10], x, y, ppar[N + 10], eup[N + 10];
ll dis[N + 10], ans[N + 10], all, sum;
ll tmpAll, lazy[4 * N + 10], sumAll, wup[N + 10];

vector<pair<int, int>> adj[N + 10];
vector<int> root;

int tim, st[N + 10], ft[N + 10], pnt[N + 10];
pair<ll, int> seg[4 * N + 10];
pair<ll, pair<int, int>> dia;

void readInput() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        int u = a[i], v = b[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        all += c[i] + d[i];
    }
}

void dfsSt(int u = 1, int par = 0, ll wUp = 0) {
    st[u] = ++tim;
    pnt[tim] = u;
    dis[u] = dis[par] + wUp;
    for (auto [v, id]: adj[u])
        if (v != par) {
            dfsSt(v, u, (a[id] == u? c[id]: d[id]));
            sumAll += (a[id] == u? d[id]: c[id]);
        }
    ft[u] = tim;
}

void calcDis(int u, int par = 0, ll wUp = 0) {
    dis[u] = dis[par] + wUp;
    for (auto [v, id]: adj[u])
        if (v != par)
            calcDis(v, u, c[id] + d[id]);
}

int calcFar(int u) {
    calcDis(u);
    int mx = 1;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[mx])
            mx = i;
    return mx;
}

void shift(int, int, int);

void update(int st, int en, ll val, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        seg[id].first += val;
        lazy[id] += val;
        return;
    }
    shift(id, l, r);
    int mid = (l + r) >> 1;
    update(st, en, val, id << 1, l, mid);
    update(st, en, val, id << 1 | 1, mid, r);
    seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

void shift(int id, int l, int r) {
    if (!lazy[id])
        return;
    int mid = (l + r) >> 1;
    update(l, r, lazy[id], id << 1, l, mid);
    update(l, r, lazy[id], id << 1 | 1, mid, r);
    lazy[id] = 0;
}

void build(int id = 1, int l = 1, int r = n + 1) {
    lazy[id] = 0;
    if (l + 1 == r) {
        seg[id] = {dis[pnt[l]], l};
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid, r);
    seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

void change(int u, int par, int up, ll f) {
    ll x = (a[up] == par? c[up]: d[up]);
    ll y = (a[up] == u? c[up]: d[up]);
    //cout << u << ": " << st[u] << ' ' << ft[u] << endl;
    update(1, n + 1, y * f);
    update(st[u], ft[u] + 1, (- x - y) * f);
    sumAll = sumAll + f * (- y + x);
}

void dfsDia(int u = 1, int par = 0, int up = 0) {
    if (u != 1)
        change(u, par, up, 1);
    pair<ll, pair<int, int>> tmp = {seg[1].first + sumAll, {u, pnt[seg[1].second]}};
    //cout << u << " === " << seg[1].first << ' ' << sumAll << " | " << pnt[seg[1].second] << ' ' << dis[u] << endl;
    dia = max(dia, tmp);
    ans[1] = max(ans[1], sumAll);
    for (auto [v, id]: adj[u])
        if (v != par)
            dfsDia(v, u, id);
    if (u != 1)
        change(u, par, up, -1);
}

void calcDiameter() {
    dfsSt();
    build();
    dia = {-INF, {0, 0}};
    dfsDia();
    x = dia.second.first;
    y = dia.second.second;
    tim = 0;
    //cout << " -> " << x << ' ' << y << endl;
}

bool dfsPath(int u, int par = 0) {
    if (u == y) {
        root.push_back(u);
        return true;
    }
    for (auto [v, id]: adj[u])
        if (v != par && dfsPath(v, u)) {
            root.push_back(u);
            sum += c[id] + d[id];
            mark[id] = true;
            return true;
        }
    return false;
}

void calcSt(int u, int par = 0, ll wUp = 0) {
    st[u] = ++tim;
    pnt[tim] = u;
    dis[u] = dis[par] + wUp;
    ppar[u] = par;
    wup[u] = wUp;
    for (auto [v, id]: adj[u])
        if (v != par && !mark[id]) {
            calcSt(v, u, (a[id] == u? c[id]: d[id]));
            sum += (a[id] == u? d[id]: c[id]);
            eup[v] = id;
        }
    ft[u] = tim;
}

void checkPath() {
    dfsPath(x);
    for (auto r: root)
        calcSt(r);
}

void init() {   
    calcDiameter();
    checkPath();
    build();
}

void delUp(int u) {
    int pnt = u;
    while (eup[pnt] && !mark[eup[pnt]]) {
        mark[eup[pnt]] = true;
        update(st[pnt], ft[pnt] + 1, -wup[pnt]);
        pnt = ppar[pnt];
    }
}

void calcAns() {
    ans[2] = all - sum;
    ans[1] = all - ans[1];
    update(st[x], st[x] + 1, -INF);
    update(st[y], st[y] + 1, -INF);
    for (int i = 3; i <= n; i++) {
        int u = pnt[seg[1].second];
        sum += seg[1].first;
        ans[i] = all - sum;
        update(st[u], st[u] + 1, -INF);
        delUp(u);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    init();
    calcAns();
    cin >> q;
    while (q--) {
        int e;
        cin >> e;
        cout << ans[e] << '\n';
    }
    cout.flush();
    return 0;
}

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