Submission #795840

#	Time	Username	Problem	Language	Result	Execution time	Memory
795840		GusterGoose27	Road Closures (APIO21_roads)	C++17	100 / 100	407 ms	60696 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ostree;

const int MAXN = 1e5+5;

vector<pii> edges[MAXN];
vector<pii> active[MAXN];
vector<int> at_deg[MAXN];
vector<int> cur_active;
ostree adj_inactive[MAXN];
bool activated[MAXN];
ll preset[MAXN];
bool vis[MAXN];
ll dp[MAXN][2];
int n;

void activate(int v, int k) {
    activated[v] = 1;
    cur_active.push_back(v);
    for (pii p: edges[v]) { // order returns num strictly less than
        int nxt = p.first;
        int ord = adj_inactive[nxt].order_of_key(pii(p.second, v));
        adj_inactive[nxt].erase(pii(p.second, v));
        if (activated[nxt]) {
            if (ord < edges[nxt].size()-k) {
                preset[nxt] -= p.second;
                if (adj_inactive[nxt].size() >= edges[nxt].size()-k) {
                    preset[nxt] += adj_inactive[nxt].find_by_order(edges[nxt].size()-k-1)->first;
                }
            }
            active[v].push_back(p);
            active[nxt].push_back(pii(v, p.second));
        }
    }
}

ll trade(int cur, int &req, int &pre_pos, ll cur_cost, bool force = 0) {
    if (req) {
        req--;
        return cur_cost;
    }
    if (pre_pos < 0) {
        if (force) {
            req = max(0, req-1);
            return cur_cost;
        }
        return 0;
    }
    // assert(pre_pos >= 0);
    int adj_cost = adj_inactive[cur].find_by_order(pre_pos)->first;
    if (cur_cost < adj_cost || force) {
        --pre_pos;
        return cur_cost-adj_cost;
    }
    return 0;
}

void dfs(int cur, int k, pii par) {
    if (vis[cur]) return;
    vis[cur] = 1;
    for (int j = 0; j < 2; j++) {
        if (par.second == -1 && j) continue;
        vector<ll> costs;
        ll ans = preset[cur];
        for (pii p: active[cur]) {
            if (p.first == par.first) continue;
            dfs(p.first, k, pii(cur, p.second));
            ans += dp[p.first][0];
            costs.push_back(dp[p.first][1]-dp[p.first][0]);
        }
        int req = max(0, (int)edges[cur].size()-k-(int)adj_inactive[cur].size());
        // cerr << cur << ' ' << req << '\n';
        int pre_pos = min((int)adj_inactive[cur].size()-1, (int)edges[cur].size()-k-1);
        if (j) {
            ans += trade(cur, req, pre_pos, par.second, 1);
        }
        else if (par.second != -1) costs.push_back(par.second);
        sort(costs.begin(), costs.end());
        for (ll cost: costs) ans += trade(cur, req, pre_pos, cost);
        assert(req == 0);
        dp[cur][j] = ans;
    }
}

void expand(int cur, int k) {
    if (adj_inactive[cur].size() >= edges[cur].size()-k)
        preset[cur] += adj_inactive[cur].find_by_order(edges[cur].size()-k-1)->first;
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    for (int i = 0; i < n-1; i++) {
        edges[U[i]].push_back(pii(V[i], W[i]));
        edges[V[i]].push_back(pii(U[i], W[i]));
        adj_inactive[U[i]].insert(pii(W[i], V[i]));
        adj_inactive[V[i]].insert(pii(W[i], U[i]));
    }
    for (int i = 0; i < n; i++) at_deg[edges[i].size()].push_back(i);
    vector<ll> ans(n, 0);
    for (int k = n-1; k >= 0; k--) {
        // cerr << "start of " << k << "\n";
        for (int v: at_deg[k+1]) activate(v, k+1);
        for (int v: cur_active) expand(v, k);
        for (int v: cur_active) {
            if (vis[v]) continue;
            dfs(v, k, pii(-1, -1));
            ans[k] += dp[v][0];
        }
        for (int v: cur_active) vis[v] = 0;
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void activate(int, int)':
roads.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             if (ord < edges[nxt].size()-k) {
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22