Submission #981394

#	Time	Username	Problem	Language	Result	Execution time	Memory
981394		Jawad_Akbar_JJ	Road Closures (APIO21_roads)	C++17	7 / 100	2096 ms	7592 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 Mn[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);
			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;
}

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){

	if (n <= 2000)
		return sub3(n,U,V,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);
}

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:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

• Subtask 1: 0 / 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