Submission #444759

#	Time	Username	Problem	Language	Result	Execution time	Memory
444759		arnold518	Road Closures (APIO21_roads)	C++17	24 / 100	2134 ms	709604 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N;
vector<pii> adj[MAXN+10];
int par[MAXN+10], val[MAXN+10], sz[MAXN+10];
ll ans[MAXN+10];

int K;
vector<ll> dp1[MAXN+10], dp2[MAXN+10];

void dfs(int now, int bef)
{
	sz[now]=1;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now);
		par[nxt.first]=now;
		val[nxt.first]=nxt.second;
		sz[now]+=sz[nxt.first];
	}
}
/*
void dfs2(int now, int bef)
{
	vector<ll> V;
	ll p=0;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs2(nxt.first, now);
		V.push_back(dp1[nxt.first]-dp2[nxt.first]);
		p+=dp2[nxt.first];
	}
	sort(V.begin(), V.end());
	for(int i=0; i<K-1 && i<V.size(); i++)
	{
		if(V[i]<0) p+=V[i];
	}
	dp1[now]=p;
	if(K-1<V.size() && V[K-1]<0) p+=V[K-1];
	dp2[now]=p+val[now];
}
*/

void dfs2(int now, int bef)
{
	vector<int> chd;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs2(nxt.first, now);
		chd.push_back(nxt.first);
	}
	sort(chd.begin(), chd.end(), [&](const int &p, const int &q)
	{
		return sz[p]>sz[q];
	});

	dp1[now]=dp2[now]=vector<ll>(sz[now]);
	for(int i=0; i<sz[now]; i++)
	{
		ll p=0;
		vector<ll> V;
		for(auto it : chd)
		{
			if(i>=dp2[it].size())
			{
				p+=val[it];
				V.push_back(-val[it]);
				continue;
			}
			p+=dp2[it][i];
			V.push_back(dp1[it][i]-dp2[it][i]);
		}
		sort(V.begin(), V.end());
		for(int j=0; j<i-1 && j<V.size(); j++)
		{
			if(V[j]<0) p+=V[j];
		}
		dp1[now][i]=p;
		if(i-1<V.size() && V[i-1]<0) p+=V[i-1];
		dp2[now][i]=p+val[now];
	}
}

vector<ll> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W)
{
	N=_N;
	for(int i=0; i<N-1; i++)
	{
		int u=_U[i], v=_V[i], w=_W[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	dfs(1, 1);
	dfs2(1, 1);
	for(int i=0; i<N; i++) ans[i]=dp2[1][i];

	return vector<ll>(ans, ans+N);
}

Compilation message (stderr)

roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:75:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    if(i>=dp2[it].size())
      |       ~^~~~~~~~~~~~~~~~
roads.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int j=0; j<i-1 && j<V.size(); j++)
      |                         ~^~~~~~~~~
roads.cpp:90:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   if(i-1<V.size() && V[i-1]<0) p+=V[i-1];
      |      ~~~^~~~~~~~~

• 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