Submission #744525

#TimeUsernameProblemLanguageResultExecution timeMemory
744525RushBRoad Closures (APIO21_roads)C++17
14 / 100
2069 ms5076 KiB
#include "roads.h" #include <bits/stdc++.h> using namespace std; const int N = 2000 + 5; long long dp[N][2]; int X; vector<array<int, 2>> adj[N]; void dfs(int v, int p) { long long dif = 0, ans = 0, mx = 0; vector<long long> V; V.reserve(adj[v].size()); for (auto P: adj[v]) if (P[0] != p) { int u = P[0], w = P[1]; dfs(u, v); dif += dp[u][0]; V.push_back(w + dp[u][1] - dp[u][0]); } sort(V.rbegin(), V.rend()); for (int i = 0; i <= X; i++) { if (i && i <= V.size()) ans += V[i - 1]; mx = max(mx, ans); if (i + 1 == X) { dp[v][1] = mx + dif; } else if (i == X) { dp[v][0] = mx + dif; } } } vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) { long long all = 0; for (int i = 0; i < n - 1; i++) { adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); all += W[i]; } vector<long long> re(n); re[0] = all; for (int i = 1; i < n; i++) X = i, dfs(0, 0), re[i] = all - dp[0][0], memset(dp, 0, sizeof dp); return re; }

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if (i && i <= V.size()) ans += V[i - 1];
      |            ~~^~~~~~~~~~~
#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...