Submission #111466

#TimeUsernameProblemLanguageResultExecution timeMemory
111466ecasdqinaFireworks (APIO16_fireworks)C++14
26 / 100
46 ms1116 KiB
#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);
                 ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...