Submission #111466

#	Time	Username	Problem	Language	Result	Execution time	Memory
111466		ecasdqina	Fireworks (APIO16_fireworks)	C++14	26 / 100	46 ms	1116 KiB

fireworks

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<int> leaf(m);
	std::vector<std::vector<std::pair<int, i64>>> g(n + m); n += m;
	for(int i = 1; i < n; i++) {
		int a; i64 b; scanf("%d%lld", &a, &b);
		
	//	g[i].push_back({a - 1, b});
		g[a - 1].push_back({i, b});
	}
	
	std::vector<i64> dist(n, 0);
	std::function<void (int, int, i64)> dfs = [&](int v, int par, i64 ari) {
		dist[v] = ari;
		for(auto e: g[v]) {
			if(e.first == par) continue;
			dfs(e.first, v, ari + e.second);
		}
	};
	dfs(0, -1, 0);
	
	i64 ans = 1LL << 60;
	if(n - m == 1) {
		std::function<i64 (std::vector<i64>&)> OSNIKTR = [](std::vector<i64>& vec) {
			i64 X = 0, Y = 1LL << 60;
			std::vector<i64> s(vec.size() + 1, 0);
			for(int i = 0; i < vec.size(); i++) s[i + 1] = s[i] + vec[i];
			
			for(i64 i = 0; i < vec.size(); i++) {
				i64 tmp = 0;
				tmp += i * vec[i] - s[i];
				tmp += (s.back() - s[i]) - ((i64)vec.size() - i) * vec[i];
				if(tmp < Y) {
					Y = tmp;
					X = vec[i];
				}
			}
			
			return X;
		};
		sort(begin(dist), end(dist));
		dist.erase(begin(dist));
		i64 makino = OSNIKTR(dist);
		
		ans = 0;
		for(auto v: dist) ans += std::abs(v - makino);
	} else if(n <= 300) {
		auto dp = make_v<i64>(n, 301);
		for(int i = 0; i < dp.size(); i++) for(int j = 0; j < dp[i].size(); j++) dp[i][j] = 1LL << 60;
		std::function<void (int)> solve = [&](int v) {
			if(v > n - m - 1) {
				dp[v][0] = 0;
				return;
			}
			
			for(auto e: g[v]) solve(e.first);
			for(int i = 0; i < dp[v].size(); i++) {
				i64 tmp = 0;
				for(auto e: g[v]) {
					i64 mi = 1LL << 60;
					for(int j = 0; j < dp[e.first].size(); j++) {
						i64 diff = i - (j + e.second);
						if(e.second + diff < 0) continue;
						mi = std::min(mi, dp[e.first][j] + std::abs(diff));
					}
					tmp += mi;
				}
				dp[v][i] = tmp;
			}
		};
		solve(0);
		
		for(auto v: dp[0]) ans = std::min(ans, v);
	} else {
		assert(0);
	}
	
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In lambda function:
fireworks.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < vec.size(); i++) s[i + 1] = s[i] + vec[i];
                   ~~^~~~~~~~~~~~
fireworks.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i64 i = 0; i < vec.size(); i++) {
                   ~~^~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dp.size(); i++) for(int j = 0; j < dp[i].size(); j++) dp[i][j] = 1LL << 60;
                  ~~^~~~~~~~~~~
fireworks.cpp:64:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dp.size(); i++) for(int j = 0; j < dp[i].size(); j++) dp[i][j] = 1LL << 60;
                                                     ~~^~~~~~~~~~~~~~
fireworks.cpp: In lambda function:
fireworks.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < dp[v].size(); i++) {
                   ~~^~~~~~~~~~~~~~
fireworks.cpp:76:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j < dp[e.first].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:17:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; i64 b; scanf("%d%lld", &a, &b);
                 ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45