이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N=1e5;
int n;
vector<vector<int>> adj[N];
int deg[N];
vector<vector<int>> edges;
multiset<ll> ex[N];
bool vis[N];
ll dp[N][2];
void dfs(int x, int k){
vis[x]=1;
vector<ll> best={-(ll)1e18};
for(auto e:adj[x]){
int v=e[0];
if(deg[v]<k) break;
if(!vis[v]){
// cout << x << "->" << v << "\n";
dfs(v, k);
dp[x][0]+=dp[v][1];
dp[x][1]+=dp[v][1];
best.push_back(dp[v][0]-dp[v][1]+e[1]);
}
}
sort(best.begin(), best.end());
vector<ll> del;
for(int i=0; i<k; i++){
ll a=*--ex[x].end();
ll b=best.back();
if(a>b){
// cout << "dp[" << x << "] use " << a << '\n';
dp[x][1]+=a;
if(i!=k-1) dp[x][0]+=a;
del.push_back(a);
ex[x].erase(--ex[x].end());
}
else{
// cout << "dp[" << x << "] use " << b << '\n';
dp[x][1]+=b;
if(i!=k-1) dp[x][0]+=b;
best.pop_back();
}
}
for(ll a:del) ex[x].insert(a);
dp[x][1]=max(dp[x][1], 0LL);
// cout << "dp[" << x << "][0] = " << dp[x][0] << "\n";
// cout << "dp[" << x << "][1] = " << dp[x][1] << "\n";
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n=N;
vector<ll> ret;
ll E=accumulate(W.begin(), W.end(), 0LL);
for(int i=0; i<n-1; i++){
edges.push_back({U[i],V[i],W[i]});
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
deg[U[i]]++;
deg[V[i]]++;
}
vector<vector<vector<int>>> ed(n);
for(int i=0; i<n; i++){
sort(adj[i].begin(), adj[i].end(), [&](vector<int> a, vector<int> b){
return deg[a[0]]>deg[b[0]];
});
ex[i].insert(-1e18);
}
for(auto e:edges){
ed[min(deg[e[1]], deg[e[0]])].push_back(e);
}
vector<int> nodes;
for(int i=0; i<n; i++) nodes.push_back(i);
for(int k=0; k<n; k++){
ll ans=0;
// cout << "k " << " " << k << "\n";
for(int x:nodes){
if(!vis[x]) dfs(x, k), ans+=dp[x][1];
}
cout << E-ans << "\n";
ret.push_back(E-ans);
for(int x:nodes) vis[x]=0, dp[x][0]=dp[x][1]=0;
for(auto e:ed[k]){
int u=e[0], v=e[1];
if(deg[u]==k && deg[v]==k){}
else if(deg[u]==k) ex[v].insert(e[2]);
else ex[u].insert(e[2]);
}
vector<int> nodes2;
for(int x:nodes){
if(deg[x]>k) nodes2.push_back(x);
}
swap(nodes, nodes2);
}
return ret;
}
// int main(){
// cin.tie(0)->sync_with_stdio(0);
// minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
// }
// nobody hears me scream
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |