Submission #981418

#	Time	Username	Problem	Language	Result	Execution time	Memory
981418		Jawad_Akbar_JJ	Road Closures (APIO21_roads)	C++17	12 / 100	2028 ms	12628 KiB

roads

#include <iostream>
#include <vector>
#include <algorithm>
// #include "roads.h"

using namespace std;
#define ll long long
const int N = 1e5 + 10;
vector<pair<int,int>> ch[N];
ll dp[N][2];

vector<ll> sub1(int n,vector<int> W){
	sort(rbegin(W),rend(W));
	vector<ll> v;
	v.push_back(0);
	for (int i : W)
		v[0] += i;
	for (int i : W)
		v.push_back(v.back() - i);
	return v;
}

vector<ll> sub2(int n,vector<int> W){
	ll t = W[0];
	ll nt = 0;
	vector<ll> v(n,0);
	v[0] += W[0];
	for (int i=1;i<n-1;i++){
		ll a = t;
		t = min(t,nt) + W[i];
		nt = a;
		v[0] += W[i];
	}
	v[1] = min(t,nt);
	return v;
}


void dfs(int u,int k,int p = -1,ll W = 1e12){
	int d = ch[u].size();
	vector<ll> Mn(d + 5,1e17);
	Mn[0] = 0;

	for (auto [i,w] : ch[u]){
		if (i == p)
			continue;
		dfs(i,k,u,w);
		for (int j=d;j>=0;j--){
			Mn[j + 1] = min(Mn[j + 1],Mn[j] + dp[i][1]);
			Mn[j + 1] = min(Mn[j + 1],Mn[j] + dp[i][0] + w);
			// cout<<u<<" link "<<i<<'\n';
			Mn[j] += dp[i][0];
		}
	}
	int to_rem = max(0,d - k);
	dp[u][0] = Mn[to_rem];
	dp[u][1] = (to_rem != 0 ? Mn[to_rem - 1] : 0) + W;

	// cout<<"vertex "<<u<<" ::: \n";
	// for (int i=0;i<d;i++)
	// 	cout<<i<<" "<<Mn[i]<<'\n';
	// cout<<"dp values "<<dp[u][0]<<" "<<dp[u][1]<<endl;
	// cout<<'\n';
}

vector<ll> sub3(int n,vector<int> U,vector<int> V,vector<int> W){
	for (int i=0;i<n-1;i++){
		ch[U[i] + 1].push_back({V[i] + 1,W[i]});
		ch[V[i] + 1].push_back({U[i] + 1,W[i]});
	}
	vector<ll> v;
	for (int k=0;k<n;k++){
		for (int i=0;i<=n;i++)
			for (int j : {0,1})
				dp[i][j] = 1e17;
		dfs(1,k);
		v.push_back(dp[1][0]);
	}
	return v;
}

vector<ll>  minimum_closure_costs(int n,vector<int> U,vector<int> V,vector<int> W){

	long long sum = 0,sum2 = 0,sum3 = 0;

	for (int i=0;i<n-1;i++)
		sum += U[i],sum2 += W[i],sum3 += (U[i] == i);
	
	if (sum == 0)
		return sub1(n,W);
	
	// if (sum2 == n-1)
	// 	return sub5(n,U,V);
	if (sum3 == n-1)
		return sub2(n,W);

	if (n <= 2000)
		return sub3(n,U,V,W);

}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^

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