제출 #570406

#제출 시각아이디문제언어결과실행 시간메모리
570406grt도로 폐쇄 (APIO21_roads)C++17
24 / 100
2079 ms22288 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second //#pragma GCC optimize ("O3") //#pragma GCC target("tune=native") //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; using namespace std; using ll = long long; using pi = pair<int, int>; using vi = vector<int>; const int nax = 100 * 1000 + 10; int n, k; vector<pi>G[nax]; ll dp[nax][2]; void dfs(int x, int p) { ll sum = 0; vector<ll>dx = {}; for(auto [nbh, w] : G[x]) if(nbh != p) { dfs(nbh, x); sum += dp[nbh][0]; if(-dp[nbh][0] + dp[nbh][1] + w > 0) dx.PB(-dp[nbh][0] + dp[nbh][1] + w); } sort(dx.rbegin(), dx.rend()); dp[x][0] = dp[x][1] = sum; for(int i = 0; i < min(k - 1, (int)dx.size()); ++i) { dp[x][1] += dx[i]; dp[x][0] += dx[i]; } if((int)dx.size() >= k && k > 0) { dp[x][0] += dx[k - 1]; } } vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) { n = N; ll sum = 0; for(int i = 0; i < n - 1; ++i) { G[U[i]].emplace_back(V[i], W[i]); G[V[i]].emplace_back(U[i], W[i]); sum += W[i]; } vector<ll>res(n); for(k = 0; k < n; ++k) { dfs(0, -1); res[k] = sum - dp[0][0]; } return res; } //int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //auto vec = minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5}); //auto vec1 = minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2}); //cin >> n; //vi u(n-1), v(n-1), w(n-1); //for(int i = 0; i < n-1; ++i) cin >> u[i] >> v[i] >> w[i]; //auto vec = minimum_closure_costs(n, u, v, w); //for(auto x : vec1) cout << x << " "; //}
#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...