제출 #724893

#제출 시각아이디문제언어결과실행 시간메모리
724893grossly_overconfident도로 폐쇄 (APIO21_roads)C++17
7 / 100
135 ms50224 KiB
//#include "roads.h" #include <bits/stdc++.h> using namespace std; #define endl '\n' //#define int long long //#define INT_MAX LONG_LONG_MAX long long findscore(multiset<pair<long long, pair<long long, long long>>>& candidates, int k, int j){ long long score = 0; for (auto i : candidates){ if (j <= k){ score += min(i.second.first, i.second.second); } else{ j--; score += i.second.second; } } return score; } long long solve(vector<vector<long long>>& dp, vector<vector<pair<int, int>>>& adj, int p, int n, int k, int i, int j){ if (dp[i][j] != -1){ return dp[i][j]; } bool ac = true; multiset<pair<long long, pair<long long, long long>>> candidates; for (auto a : adj[i]){ if (a.first != p){ ac = false; long long op1 = solve(dp, adj, i, n, k, a.first, adj[a.first].size()); long long op2 = solve(dp, adj, i, n, k, a.first, adj[a.first].size() - 1) + a.second; candidates.insert({op2 - op1, {op1, op2}}); } } if (ac){ return 0; } return dp[i][j] = findscore(candidates, k, j); } vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w){ vector<long long> out(n); vector<vector<pair<int, int>>> adj(n); 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]}); } /* int leaf = 0; for (int i = 0; i < n; ++i){ if (adj[i].size() == 1){ leaf = i; break; } } */ vector<vector<long long>> dp(n + 10, vector<long long>(5, -1)); out[0] = solve(dp, adj, -1, n, 0, 0, adj[0].size()); vector<vector<long long>> dp2(n + 10, vector<long long>(5, -1)); out[1] = solve(dp2, adj, -1, n, 1, 0, adj[0].size()); return out; } /* int main(){ int n; cin >> n; vector<int> u(n - 1), v(n - 1), w(n - 1); for (int i = 0; i < n - 1; ++i){ cin >> u[i]; } for (int i = 0; i < n - 1; ++i){ cin >> v[i]; } for (int i = 0; i < n - 1; ++i){ cin >> w[i]; } vector<long long> out; out = minimum_closure_costs(n, u, v, w); for (auto a : out){ cout << a << " "; } return 0; } */
#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...