Submission #165086

#	Time	Username	Problem	Language	Result	Execution time	Memory
165086		EntityIT	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	674 ms	59232 KiB

designated_cities

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#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<vector<pair<LL, int> > > mx;
vector<LL> down, up, ans;
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 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_back(mx[v].back() );
    }
    mx[u].emplace_back(down[u], u);
    sort(all(mx[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);

    int root = 0;
    LL curAns = 0;
    for (int u = 1; u <= n; ++u) if (down[root] + up[root] < down[u] + up[u]) {
        root = u;
        curAns = down[u] + up[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] = down[root] + up[root];
        else query.emplace_back(e, i);
    }
    sort(query.begin(), query.end() );

    par.assign(n + 5, 0);
    mx.assign(n + 5, {} );
    down[root] = up[root] = 0; dfs(root, root);

//    cerr << "root = " << root << '\n';

    priority_queue<pair<LL, int> > pq;
    int nMark = 0;

    while (nMark < 2) {
        int u = mx[root].back().se;
        LL cost = mx[root].back().fi;

//        cerr << "u = " << u << "  cost = " << cost << '\n';

        curAns += cost;
        while (u) {
//            cerr << u << "\n";
            int pr = par[u];
            par[u] = 0;
            mx[u].pop_back();

            u = pr;
        }

//        for (u = 1; u <= n; ++u) {
//            cerr << "u = " << u << ' ';
//            for (auto _ : mx[u]) cerr << _.se << ' ';
//            cerr << '\n';
//        }

        ++nMark;
    }

    for (int u = 1; u <= n; ++u) if (!par[u]) {
        if (sz(mx[u]) ) {
            pq.emplace(mx[u].back().fi - down[u], mx[u].back().se);
//            cerr << mx[u].back().se << "???\n";
        }
    }

    for (auto que : query) {
        int e = que.fi, id = que.se;
//        cerr << "id = " << id << '\n';
        while (nMark < e) {
            assert(sz(pq) );
            int u = pq.top().se;
            LL cost = pq.top().fi;
            pq.pop();
            curAns += cost;

//            cerr << "u = " << u << ' ' << cost << '\n';

            while (u) {
//                cerr << u << ' ' << par[u] << '\n';
                int pr = par[u];
                par[u] = 0;
                mx[u].pop_back();
                if (sz(mx[u]) ) {
                    pq.emplace(mx[u].back().fi - down[u], mx[u].back().se);
                }

                u = pr;
            }

//            for (u = 1; u <= n; ++u) {
//                cerr << "u = " << u << '\n';
//                for (auto _ : mx[u]) cerr << _.se << ' ';
//                cerr << '\n';
//            }

            ++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