제출 #446323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446323		koioi.org-koosaga	도로 폐쇄 (APIO21_roads)	C++17	24 / 100	2083 ms	16060 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);
	for(int k = N - 1; k > 0; k--){
		for(auto &j : dfn){
			vector<lint> v;
			for(auto &[w, s] : gph[j]){
				ans[k] += w;
				v.push_back(min(0ll, dp[s] - w));
			}
			sort(all(v));
			for(int j = 0; j < min(sz(v), k); j++) ans[k] += v[j];
			dp[j] = -(sz(v) >= k ? v[k-1] : 0);
		}
	}
	return ans;
}

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

vector<pi> gph[MAXN];
vector<int> ord;
int par[MAXN], pae[MAXN];

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

lint dp[MAXN];

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);
	vector<multiset<lint>> vect(N);
	reverse(all(ord));
	ans[0] = accumulate(pae, pae + N, 0ll);
	for(auto &v : ord){
		for(int q = 0; q < sz(gph[v]); q++) vect[v].insert(0);
	}
	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);
	};
	ans[0] = accumulate(pae, pae + N, 0ll);
	lint ret = 0;
	for(int i = N-1; i >= 1; i--){
		for(auto &v : ord){
			if(sz(gph[v]) <= i) continue;
			ret -= getkth(vect[v], i);
			ret -= getsum(vect[par[v]], i);
			ret += dp[v];


			if(v) vect[par[v]].erase(vect[par[v]].find(dp[v]));
			dp[v] = 0;
			dp[v] -= pae[v];
			dp[v] -= getkth(vect[v], i);
			if(v) vect[par[v]].insert(dp[v]);

			ret -= dp[v];
			ret += getsum(vect[par[v]], i);
		}
		ans[i] = ret;
	}
	return ans;
}
*/

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