Submission #165063

#	Time	Username	Problem	Language	Result	Execution time	Memory
165063		EntityIT	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	686 ms	73868 KiB

designated_cities

#include<bits/stdc++.h>

using namespace std;

#define sz(x) ( (int)(x).size() )
#define fi first
#define se second
using LL = long long;

int n, q;
LL sumCost = 0;
vector<int> par;
vector<vector<int> > gr;
vector<multiset<pair<LL, int> > > mx;
vector<LL> down, up, ans, val;
vector<pair<int, int> > query;
struct Edge {
    int to, cost;
    Edge(int _to = 0, int _cost = 0) : to(_to), cost(_cost) {}
};
vector<Edge> edge;

void calDown(int u, int pr) {
    for (int i : gr[u]) {
        int v = edge[i].to, cost = edge[i ^ 1].cost;
        if (v == pr) continue ;
        calDown(v, u);
        down[u] += down[v] + cost;
    }
}

void calUp(int u, int pr) {
    for (int i : gr[u]) {
        int v = edge[i].to, cost = edge[i ^ 1].cost;
        if (v == pr) continue ;
        up[v] = up[u] + down[u] - down[v] - cost + edge[i].cost;
        calUp(v, u);
    }
}

void calVal(int u, int pr) {
    for (int i : gr[u]) {
        int v = edge[i].to;
        if (v == pr) continue ;
        val[v] = val[u] + edge[i].cost + edge[i ^ 1].cost;
    }
}

void dfs(int u, int pr) {
    for (int i : gr[u]) {
        int v = edge[i].to, cost = edge[i].cost;
        if (v == pr) continue ;
        par[v] = u;
        down[v] = down[u] + cost;
        up[v] = up[u] + edge[i ^ 1].cost;
        dfs(v, u);
        mx[u].emplace(*mx[v].rbegin() );
    }
    mx[u].emplace(down[u], u);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("input", "r", stdin);
//    freopen("output", "w", stdout);

    cin >> n;

    gr.assign(n + 5, vector<int>() );
    for (int i = 0; i < n - 1; ++i) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        sumCost += c; sumCost += d;
        gr[u].emplace_back(sz(edge) ); edge.emplace_back(v, c);
        gr[v].emplace_back(sz(edge) ); edge.emplace_back(u, d);
    }

    down.assign(n + 5, 0);
    up.assign(n + 5, 0);
    calDown(1, 1);
    calUp(1, 1);

//    for (int u = 1; u <= n; ++u) cerr << up[u] << ' ' << down[u] << '\n';

    LL ans1 = 0;
    for (int u = 1; u <= n; ++u) ans1 = max(ans1, up[u] + down[u]);

    cin >> q;
    query.reserve(q);
    ans.assign(q, 0);
    for (int i = 0; i < q; ++i) {
        int e; cin >> e;
        if (e == 1) ans[i] = ans1;
        else query.emplace_back(e, i);
    }
    sort(query.begin(), query.end() );

    val.assign(n + 5, 0);
    calVal(1, 1);

    int root = 0;
    for (int u = 1; u <= n; ++u) if (val[root] < val[u]) root = u;

    par.assign(n + 5, 0);
    mx.assign(n + 5, {} );
    dfs(root, root);

    priority_queue<pair<LL, int> > pq;
    pq.emplace(*mx[root].rbegin() );

    int nMark = 1;
    LL curAns = up[root];
    for (auto _ : query) {
        int e = _.fi, id = _.se;
        while (nMark < e) {
            assert(sz(pq) );
            int u = pq.top().se;
            LL cost = pq.top().fi;
            curAns += cost;

            while (u) {
                int pr = par[u];
                par[u] = 0;
                mx[u].erase(prev(mx[u].end() ) );
                if (sz(mx[u]) ) pq.emplace(mx[u].rbegin()->fi - down[u], mx[u].rbegin()->se);

                u = pr;
            }

            ++nMark;
        }
        ans[id] = curAns;
    }

    for (int i = 0; i < q; ++i) cout << sumCost - ans[i] << '\n';

    return 0;
}

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