Submission #982646

#	Time	Username	Problem	Language	Result	Execution time	Memory
982646		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	2080 ms	35480 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<pair<long long, long long>> g[400001];
vector<long long> v;
long long n, i, j;
long long dp[400001][2];

void dfs(long long x, long long pr, long long k, long long c) {
	vector<long long> vv, vv2;
	for (auto y : g[x]) {
		if (y.first == pr) continue;
		dfs(y.first, x, k, y.second);
		dp[x][0] += dp[y.first][0];
		dp[x][1] += dp[y.first][0];
	}
	for (auto y : g[x]) {
		if (y.first == pr) continue;
		vv.push_back({-dp[y.first][0] + dp[y.first][1] + y.second});
		if (-dp[y.first][0] + dp[y.first][1] + y.second < 0) vv2.push_back({-dp[y.first][0] + dp[y.first][1] + y.second});
	}
	sort(vv.begin(), vv.end());
	for (long long i = 0; i < vv2.size(); i++) {
		dp[x][0] += vv2[i];
		dp[x][1] += vv2[i];
	}
	long long w = (long long)vv.size() - (long long)vv2.size() - k;
	for (long long i = 0; i < vv.size(); i++) {
		if (i <= (long long)vv.size() - (long long)vv2.size() - k) dp[x][0] += vv[i];
	}
	for (long long i = 0; i < vv.size(); i++) {
		if (i < (long long)vv.size() - (long long)vv2.size() - k) dp[x][1] += vv[i];
	}
	//cout << x << " " << dp[x][0] << " " << dp[x][1] << "\n";
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	long long s = 0;
	for (long long i = 0; i < N - 1; i++) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
	}
	for (long long i = 0; i < N; i++) {
		for (long long j = 0; j <= N; j++) dp[j][0] = dp[j][1] = 0;
		dfs(0, 0, i, 0);
		v.push_back(dp[0][1]);
	}
	reverse(v.begin(), v.end());
	assert(is_sorted(v.begin(), v.end()));
	reverse(v.begin(), v.end());
  return v;
}

/*
 *
5
0 1 1
0 2 4
0 3 3
2 4 2

 * */

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
roads.cpp:24:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (long long i = 0; i < vv2.size(); i++) {
      |                        ~~^~~~~~~~~~~~
roads.cpp:29:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (long long i = 0; i < vv.size(); i++) {
      |                        ~~^~~~~~~~~~~
roads.cpp:32:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (long long i = 0; i < vv.size(); i++) {
      |                        ~~^~~~~~~~~~~
roads.cpp:28:12: warning: unused variable 'w' [-Wunused-variable]
   28 |  long long w = (long long)vv.size() - (long long)vv2.size() - k;
      |            ^
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:40:12: warning: unused variable 's' [-Wunused-variable]
   40 |  long long s = 0;
      |            ^

• 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