| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 726016 | SanguineChameleon | Road Closures (APIO21_roads) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
struct segtree {
int N, rem, node_id;
vector<int> val;
void init(int _node_id, vector<pair<int, int>> &pre_adj) {
node_id = _node_id;
N = pre_adj.size();
rem = N;
val.resize(N);
for (int i = 0; i < N; i++) {
val[i] = pre_adj[i].first;
}
}
void update(int pos) {
val[pos] = 0;
rem--;
}
long long get(int x) {
x = max(x, 0);
if (x == 0) {
return 0;
}
if (x > rem) {
return inf;
}
long long res = 0;
int cnt = 0;
for (int i = 0; i < N; i++) {
if (val[i]) {
res += val[i];
cnt++;
if (cnt == x) {
break;
}
}
}
return res;
}
};
vector<pair<int, int>> adj[maxN];
vector<pair<int, int>> pre_adj[maxN];
segtree tree[maxN];
vector<int> bucket[maxN];
int deg[maxN];
bool is_bad[maxN];
bool flag[maxN];
long long dp[maxN][2];
int K;
void dfs(int u, int par) {
flag[u] = true;
dp[u][0] = inf;
dp[u][1] = inf;
long long sum = 0;
vector<long long> cost;
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (v == par) {
continue;
}
dfs(v, u);
sum += dp[v][1];
cost.push_back(dp[v][0] + w - dp[v][1]);
}
sort(cost.begin(), cost.end());
int cnt = deg[u] - (par != -1);
for (int i = 0; i < 2; i++) {
dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
}
for (auto w: cost) {
sum += w;
cnt--;
for (int i = 0; i < 2; i++) {
dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
}
}
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < N - 1; i++) {
pre_adj[U[i]].push_back({W[i], V[i]});
pre_adj[V[i]].push_back({W[i], U[i]});
deg[U[i]]++;
deg[V[i]]++;
}
for (int i = 0; i < N; i++) {
sort(pre_adj[i].begin(), pre_adj[i].end());
tree[i].init(i, pre_adj[i]);
bucket[deg[i]].push_back(i);
}
vector<long long> res(N);
vector<int> bad;
for (K = N - 1; K >= 0; K--) {
for (auto u: bad) {
flag[u] = false;
}
for (auto u: bad) {
if (!flag[u]) {
dfs(u, -1);
res[K] += dp[u][0];
}
}
for (auto u: bucket[K]) {
for (auto e: pre_adj[u]) {
int v = e.second;
int w = e.first;
if (is_bad[v]) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
tree[u].update(lower_bound(pre_adj[u].begin(), pre_adj[u].end(), make_pair(w, v)) - pre_adj[u].begin());
tree[v].update(lower_bound(pre_adj[v].begin(), pre_adj[v].end(), make_pair(w, u)) - pre_adj[v].begin());
}
}
bad.push_back(u);
is_bad[u] = true;
}
}
return res;
}