제출 #446341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446341		koioi.org-koosaga	Road Closures (APIO21_roads)	C++17	100 / 100	337 ms	40384 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;

struct jaryoguzo{
	multiset<lint> s, exc;
	int cur_thres;
	lint sumS;
	void init(int n){
		cur_thres = n;
	}
	void insert(lint x){
		sumS += x;
		s.insert(x);
		if(sz(s) > cur_thres){
			sumS -= *s.rbegin();
			exc.insert(*s.rbegin());
			s.erase(--s.end());
		}
	}
	void erase(lint x){
		if(exc.find(x) != exc.end()){
			exc.erase(exc.find(x));
		}
		else{
			sumS -= x;
			s.erase(s.find(x));
			if(sz(exc)){
				sumS += *exc.begin();
				s.insert(*exc.begin());
				exc.erase(exc.begin());
			}
		}
	}
	void shrink(){
		if(sz(s) == cur_thres){
			sumS -= *s.rbegin();
			exc.insert(*s.rbegin());
			s.erase(--s.end());
		}
		cur_thres--;
	}
	lint get_sum(){
		return sumS;
	}
	lint get_pos(){
		if(sz(s) == cur_thres) return *s.rbegin();
		return 0;
	}
}ds[MAXN];

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);
	for(int i = 0; i < N; i++) ds[i].init(sz(gph[i]));
	for(int i = 1; i < N; i++){
		dp[i] = -pae[i];
		ds[par[i]].insert(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){
				lint val = ds[j].get_pos();
				ans[k] -= val;
				ds[j].shrink();
			}
		}
		for(auto &j : cnd[k]){
			if(j != 0){
				ans[k] -= ds[par[j]].get_sum();
				ds[par[j]].erase(dp[j]);
			}
			if(sz(gph[j]) == k - 1) dp[j] = -pae[j];
			else dp[j] = min(-ds[j].get_pos() - pae[j], 0ll);
			if(j != 0){
				ds[par[j]].insert(dp[j]);
				ans[k] += ds[par[j]].get_sum();
			}
		}
	}
	return ans;
}

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