Submission #736358

#TimeUsernameProblemLanguageResultExecution timeMemory
736358hoainiemRoad Closures (APIO21_roads)C++14
0 / 100
63 ms65784 KiB
#include "roads.h" #include <bits/stdc++.h> #define fi first #define se second #define nmax 100008 const long long inf = 1e18; using namespace std; typedef pair<long long, long long> pii; long long n, sub1 = true; long long dp[2008][2008][2]; vector<pii> l[nmax]; long long dq(int id, int x, int pre, int kt){ if (dp[id][x][kt] != -1) return dp[id][x][kt]; if (!id && kt) return dp[id][x][kt] = inf; long long res = 0; vector<long long>vt; for (pii it : l[x]) if (it.fi != pre){ res += dq(id, it.fi, x, 1); vt.push_back(dq(id, it.fi, x, 0) + it.se - dq(id, it.fi, x, 1)); } sort(vt.begin(), vt.end(), greater<long long>()); while (!vt.empty() && ((int)vt.size() + kt > id || vt.back() < 0)){ res += vt.back(); vt.pop_back(); } return dp[id][x][kt] = res; } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; for (long long i = 0; i < n - 1; i++){ if (U[i] != 0) sub1 = false; l[U[i]].push_back({V[i], W[i]}); l[V[i]].push_back({U[i], W[i]}); } vector<long long>res; if (sub1){ sort(W.begin(), W.end(), greater<int>()); long long j = accumulate(W.begin(), W.end(), 0); res.push_back(j); for (long long i = 0; i < n - 1; i++){ j -= W[i]; res.push_back(j); } return res; } assert(n <= 2000); memset(dp, -1, sizeof(dp)); for (long long k = 0; k < n; k++) res.push_back(dq(k, 0, 0, 0)); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...