# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
563947 | 2022-05-18T09:56:32 Z | minhcool | Road Closures (APIO21_roads) | C++17 | 52 ms | 18192 KB |
#include "roads.h" #include<bits/stdc++.h> using namespace std; //#define int long long #define fi first #define se second #define pb push_back typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7; int n; vector<ii> Adj[N]; int k; int dp[N][2]; void dfs(int u, int p){ int we; for(auto it : Adj[u]){ int v = it.fi; if(v == p){ we = it.se; continue; } dfs(v, u); } vector<int> vc; int sum = 0; for(auto it : Adj[u]){ int v = it.fi; if(v == p) continue; sum += dp[v][0]; vc.pb(dp[v][0] - dp[v][1]); } sort(vc.begin(), vc.end()); reverse(vc.begin(), vc.end()); int sum2 = 0; for(int i = 0; i < min((int)Adj[u].size(), k - 1); i++){ sum2 += max(0, vc[i]); } dp[u][0] = sum - sum2 - ((Adj[u].size() < k) ? 0 : max(0, vc[k - 1])) + we; dp[u][1] = sum - sum2; } vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W){ n = N; for(int i = 0; i < (n - 1); i++){ Adj[U[i]].pb({V[i], W[i]}); Adj[V[i]].pb({U[i], W[i]}); } vector<long long> ans; for(int i = 0; i < n; i++){ k = i; dfs(1, 1); ans.pb(min(dp[i][0], dp[i][1])); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 5132 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 5076 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 5076 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 5076 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 52 ms | 18192 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 52 ms | 18192 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 5132 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |