제출 #1133807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133807		Math4Life2020	Road Closures (APIO21_roads)	C++20	0 / 100	2096 ms	18908 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 1e5+5; ll N;
const ll K = 300;
ll ans[Nm];

vector<pii> adj[Nm];
vector<ll> fadj[Nm];
ll deg[Nm];
pii radj[Nm]; //{number, cost}
vector<ll> itpl; //inverse topological sort

ll slvH(ll k) {
	ll dp0[N]; //no path up
	ll dp1[N]; //path up
	for (ll i=(N-1);i>=0;i--) {
		ll x = itpl[i];
		vector<ll> vaug; //augment vector
		ll val0 = 0; //minimum value
		for (ll y: fadj[x]) {
			val0 += dp0[y];
			vaug.push_back(dp1[y]-dp0[y]);
		}
		sort(vaug.begin(),vaug.end());
		ll NDEL = max(0LL,deg[x]-k);
		dp0[x]=val0;
		for (ll j=0;j<NDEL;j++) {
			dp0[x]+=vaug[j];
		}

		NDEL = max(0LL,deg[x]-k-1);
		dp1[x]=val0+radj[x].second;
		for (ll j=0;j<NDEL;j++) {
			dp1[x]+=vaug[j];
		}
	}
	return dp0[0];
}

vector<ll> minimum_closure_costs(int N1, vector<int> U, vector<int> V, vector<int> W) {
	N=N1;
	ll sroad = 0;
	for (ll i=0;i<(N-1);i++) {
		adj[U[i]].push_back({V[i],W[i]});
		adj[V[i]].push_back({U[i],W[i]});
		sroad += W[i];
	}
	for (ll i=0;i<N;i++) {
		deg[i]=adj[i].size();
	}
	queue<ll> q0;
	q0.push(0); //root is 0
	radj[0]={-1,-1};
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		itpl.push_back(x);
		for (pii p0: adj[x]) {
			if (p0.first!=radj[x].first) {
				fadj[x].push_back(p0.first);
				radj[p0.first]={x,p0.second};
				q0.push(p0.first);
			}
		}
	}
	for (ll k=1;k<N;k++) {
		ans[k]=slvH(k);
	}
	ans[0]=sroad;
	vector<ll> ansF(N,0);
	for (ll i=0;i<N;i++) {
		ansF[i]=ans[i];
	}
	return ansF;
}

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