Submission #434193

#	Time	Username	Problem	Language	Result	Execution time	Memory
434193		dqhungdl	Road Closures (APIO21_roads)	C++17	0 / 100	2071 ms	21968 KiB

roads

#include "roads.h"

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

typedef pair<int,int> ii;
const int MAX=1e5+5;
const long long INF=1e18;
vector<long long> f0,f1; // f0: do not need to close parent edge, f1: force to close parent edge (f0[u] >= f1[u])
vector<ii> g[MAX];

void dfs(int u,int p,int atMost) {
	long long sum=0;
	for(ii edge:g[u]) {
		int v=edge.first,w=edge.second;
		if(v==p)
			continue;
		dfs(v,u,atMost);
		sum+=f0[v];
	}
	int eraseNum=(int)g[u].size()-atMost;
	if(eraseNum<=0) {
		f0[u]=f1[u]=0;
		return;
	}
	vector<long long> gaps;
	for(ii edge:g[u]) {
		int v=edge.first,w=edge.second;
		if(v==p)
			continue;
		// Cost for switching from 0 to 1
		gaps.push_back(f1[v]+w-f0[v]);
	}
	sort(gaps.begin(),gaps.end());
	// Iterate number of erase edges
	if(eraseNum==1)
		f1[u]=0;
	long long sumGap=0;
	for(int i=0;i<gaps.size();i++) {
		sumGap+=gaps[i];
		if(i+2>=eraseNum)
			f1[u]=min(f1[u],sum+sumGap);
		if(i+1>=eraseNum)
			f0[u]=min(f0[u],sum+sumGap);
	}
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
	for(int i=0;i<N-1;i++) {
		g[U[i]].push_back({V[i],W[i]});
		g[V[i]].push_back({U[i],W[i]});
	}
	vector<long long> rs;
	for(int i=0;i<N;i++) {
		f0.resize(N,INF);
		f1.resize(N,INF);
		dfs(0,0,i);
		//for(int j=0;j<N;j++)
		//	cerr<<j<<": "<<f0[j]<<' '<<f1[j]<<'\n';
		rs.push_back(f0[0]);
	}
	return rs;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:15:20: warning: unused variable 'w' [-Wunused-variable]
   15 |   int v=edge.first,w=edge.second;
      |                    ^
roads.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<gaps.size();i++) {
      |              ~^~~~~~~~~~~~

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