제출 #735930

#제출 시각아이디문제언어결과실행 시간메모리
735930hoainiem도로 폐쇄 (APIO21_roads)C++14
0 / 100
307 ms203036 KiB
#include "roads.h" #include <bits/stdc++.h> #define fi first #define se second #define nmax 100008 using namespace std; typedef pair<long long, long long> pii; long long n; long long dp[2008][2008]; vector<long long>vt[2008][2008]; vector<pii> l[nmax]; void dfs(long long id, long long x, long long pre){ dp[id][x] = 0; for (pii it : l[x]) if (it.fi != pre){ dfs(id, it.fi, x); if (!id) dp[id][x] += dp[id][it.fi] + it.se; else{ dp[id][x] += dp[id - 1][it.fi]; vt[id][x].push_back(dp[id][it.fi] + it.se - dp[id - 1][it.fi]); } } sort(vt[id][x].begin(), vt[id][x].end(), greater<long long>()); while (!vt[id][x].empty() && ((long long)vt[id][x].size() > id || vt[id][x].back() < 0)){ dp[id][x] += vt[id][x].back(); vt[id][x].pop_back(); } } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { assert((n = N) <= 2000); for (long long i = 0; i < n - 1; i++){ l[U[i]].push_back({V[i], W[i]}); l[V[i]].push_back({U[i], W[i]}); } vector<long long>res; for (long long k = 0; k < n; k++){ dfs(k, 0, 0); res.push_back(dp[k][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...