Submission #444757

#	Time	Username	Problem	Language	Result	Execution time	Memory
444757		arnold518	Road Closures (APIO21_roads)	C++17	24 / 100	2083 ms	22504 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;
ll sum=0;
vector<pii> adj[MAXN+10];
int par[MAXN+10], val[MAXN+10];
ll ans[MAXN+10];

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

void dfs(int now, int bef)
{
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now);
		par[nxt.first]=now;
		val[nxt.first]=nxt.second;
	}
}

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(), greater<ll>());
	for(int i=0; i<K-1 && i<V.size(); i++)
	{
		if(V[i]>0) p+=V[i];
	}
	dp1[now]=p+val[now];
	if(K-1<V.size() && V[K-1]>0) p+=V[K-1];
	dp2[now]=p;
}

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});
		sum+=w;
	}

	dfs(1, 1);
	for(K=0; K<N; K++)
	{
		dfs2(1, 1);
		ans[K]=sum-dp2[1];
	}

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

Compilation message (stderr)

roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0; i<K-1 && i<V.size(); i++)
      |                        ~^~~~~~~~~
roads.cpp:48:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  if(K-1<V.size() && V[K-1]>0) p+=V[K-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