| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 423840 | hhhhaura | Road Closures (APIO21_roads) | C++14 | 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.
#define wiwihorz
#include "roads.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define INF 1e12
#define eps (1e-9)
#define MOD 1000000007
using namespace std;
#define int long long int
#define pii pair<int, int>
#define radom mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
struct ac {
int sum, x, cnt;
priority_queue<int> pq;
stack<int> st;
void init_() {
sum = 0, x = 0, cnt = 0;
while(st.size()) st.pop();
while(pq.size()) pq.pop();
}
void maintain() {
while(pq.size() > x) {
int cur = pq.top(); pq.pop();
sum -= cur;
}
}
void set(int _x) { x = max(0ll, _x); }
void add(int v) { pq.push(v), sum += v; }
void pop() {
if(!pq.size()) return;
int cur = pq.top(); pq.pop();
st.push(cur), cnt ++;
sum -= cur;
}
void redo() {
assert(cnt), cnt --;
int cur = st.top(); st.pop();
sum += cur, pq.push(cur);
}
int get_val(bool yes) {
maintain();
return sum - yes * (pq.size() ? pq.top() : 0);
}
};
namespace solver {
int n, ii, temp;
vector<int> pri, dp0, dp1, deg, vis, es, cost;
vector<vector<int>> mp;
vector<ac> s;
void init_(int _n) {
n = _n, ii = 0;
pri.assign(n, 0);
dp0.assign(n + 1, 0);
dp1.assign(n + 1, 0);
deg.assign(n + 1, 0);
vis.assign(n + 1, 0);
s.assign(n + 1, ac());
mp.assign(n + 1, vector<int>());
rep(i, 1, n) {
pri[i - 1] = i;
s[i].init_();
}
}
void add_edge(int a, int b, int c) {
mp[a].push_back(es.size());
mp[b].push_back(es.size());
es.push_back(a ^ b);
cost.push_back(c);
deg[a] ++, deg[b] ++;
}
void dfs(int x, int par, int k) {
vis[x] = k + 1;
dp1[x] = INF, dp0[x] = INF;
vector<int> v;
int cnt = 0, sum = 0;
for(auto i : mp[x]) if(i != par) {
int to = es[i] ^ x;
if(deg[to] <= k) break;
dfs(to, i, k);
v.push_back(dp1[to] + cost[i] - dp0[to]);
sum += dp0[to], cnt ++;
}
sort(all(v));
s[x].set(deg[x] - k);
s[x].maintain();
int to = s[x].x - s[x].pq.size();
if(v.size() >= to) {
int cur = 0;
rep(i, 0, to - 1) cur += v[i];
dp0[x] = min(dp0[x], sum + cur + s[x].get_val(0));
rep(j, to, cnt - 1) {
cur += v[j];
s[x].pop(), s[x].set(s[x].x - 1);
dp0[x] = min(dp0[x], sum + cur + s[x].get_val(0));
}
s[x].set(deg[x] - k);
while(s[x].cnt) s[x].redo();
}
s[x].set(deg[x] - k - 1);
s[x].maintain();
to = s[x].x - s[x].pq.size();
if(v.size() >= to) {
int cur = 0;
rep(i, 0, to - 1) cur += v[i];
dp1[x] = min(dp1[x], sum + cur + s[x].get_val(0));
rep(j, to, cnt - 1) {
cur += v[j];
s[x].pop(), s[x].set(s[x].x - 1);
dp1[x] = min(dp1[x], sum + cur + s[x].get_val(0));
}
s[x].set(deg[x] - k - 1);
while(s[x].cnt) s[x].redo();
}
}
vector<int> solve() {
sort(all(pri), [](int a, int b) {return deg[a] < deg[b];});
rep(i, 1, n) temp = i, sort(all(mp[i]),
[](int a, int b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
vector<int> aa(n, 0);
rep(i, 0, n - 1) {
while(ii < n && deg[pri[ii]] <= i) {
dp0[pri[ii]] = 0;
dp1[pri[ii]] = 0;
for(auto j : mp[pri[ii]]) {
int to = es[j] ^ pri[ii];
if(deg[to] > i) s[to].add(cost[j]);
}
ii++;
}
int ans = 0;
rep(j, ii, n - 1) if(vis[pri[j]] != i + 1){
dfs(pri[j], -1, i);
ans += dp0[pri[j]];
}
aa[i] = ans;
}
return aa;
}
};
using namespace solver;
vector<int> minimum_closure_costs(signed N, vector<int> U, vector<int> V, vector<int> W) {
init_(N);
rep(i, 0, N - 2) add_edge(U[i] + 1, V[i] + 1, W[i]);
return solve();
}