Submission #1310883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310883		thelegendary08	Road Closures (APIO21_roads)	C++20	24 / 100	2098 ms	25124 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 1e5 + 5; 
vector<pair<int,int>>adj[mxn]; int n, k; int dp[mxn][2];
void dfs(int node, int from){
	int sum = 0, deg = 0; vi dif; 
	for(auto [u,w] : adj[node])if(u!=from)dfs(u,node), deg++, sum+=max(dp[u][0],dp[u][1]), dif.pb(dp[u][0]+w-max(dp[u][0],dp[u][1])); sort(dif.rbegin(),dif.rend());
	if(deg >= k){
		dp[node][1]=sum; f0r(i,k)dp[node][1]+=dif[i];
	}
	dp[node][0]=sum; f0r(i,min(k-1,(int)dif.size())){
		if(dif[i]<0)break; dp[node][0]+=dif[i];
	}
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
                                             std::vector<signed> V,
                                             std::vector<signed> W) {
	n=N; vi ans; int S = 0; f0r(i,n-1)adj[U[i]].eb(V[i],W[i]),adj[V[i]].eb(U[i],W[i]),S+=W[i]; f0r(K,n){
		k=K; f0r(i,n)f0r(j,2)dp[i][j]=0; dfs(0,-1); ans.pb(S-max(dp[0][0],dp[0][1]));
	} 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