제출 #446340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446340		koioi.org-koosaga	도로 폐쇄 (APIO21_roads)	C++17	31 / 100	2085 ms	34912 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 100005;

lint dp[MAXN];
int par[MAXN], pae[MAXN];
vector<pi> gph[MAXN];
vector<int> dfn;

void dfs(int x, int p = -1){
	dfn.push_back(x);
	for(auto &[w, y] : gph[x]){
		pae[y] = w;
		par[y] = x;
		gph[y].erase(find(all(gph[y]), pi(w, x)));
		dfs(y, x);
	}
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    for(int i = 0; i < N - 1; i++){
    	gph[U[i]].emplace_back(W[i], V[i]);
    	gph[V[i]].emplace_back(W[i], U[i]);
	}
	dfs(0);
	vector<lint> ans(N);
	reverse(all(dfn));
	ans[0] = accumulate(all(W), 0ll);

	vector<vector<int>> cnd(N);
	vector<multiset<lint>> ds(N);
	vector<lint> sum(N);
	auto getsum = [&](multiset<lint> &ms, int k){
		lint ret = 0;
		auto it = ms.begin();
		while(k-- && it != ms.end()){
			ret += min(*it, 0ll);
			it++;
		}
		return ret;
	};
	auto getkth = [&](multiset<lint> &ms, int k){
		return getsum(ms, k) - getsum(ms, k-1);
	};
	for(int i = 1; i < N; i++){
		dp[i] = -pae[i];
		ds[par[i]].insert(dp[i]);
		sum[par[i]] += dp[i];
	}
	for(auto &i : dfn){
		for(int j = 0; j <= sz(gph[i]) + 1 && j < N; j++) cnd[j].push_back(i);
	}
	for(int k = N - 2; k > 0; k--){
		ans[k] = ans[k + 1];
		for(auto &j : cnd[k]){
			if(sz(gph[j]) > k){
				ans[k] -= getkth(ds[j], k+1);
				sum[j] -= getkth(ds[j], k+1);
			}
		}
		for(auto &j : cnd[k]){
			if(j != 0){
				ans[k] -= sum[par[j]];
				ds[par[j]].erase(ds[par[j]].find(dp[j]));
			}
			dp[j] = min(-getkth(ds[j], k) - pae[j], 0ll);
			if(j != 0){
				ds[par[j]].insert(dp[j]);
				sum[par[j]] = getsum(ds[par[j]], k);
				ans[k] += sum[par[j]];
			}
		}
	}
	return ans;
}

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