Submission #855959

#TimeUsernameProblemLanguageResultExecution timeMemory
855959lolismekPaths (RMI21_paths)C++14
0 / 100
1 ms604 KiB
#include <iostream> #include <vector> #pragma GCC optimize("Ofast") #define pii pair <long long, int> using namespace std; const int NMAX = 2000; vector <pii> adj[NMAX + 1]; int edg[NMAX + 1]; int par[NMAX + 1]; int lin[NMAX + 1]; long long v[NMAX + 1]; pii tm[NMAX + 1]; int dfsTime; void dfs(int node, int parent){ par[node] = parent; lin[++dfsTime] = node; tm[node].first = dfsTime; for(pii child : adj[node]){ if(child.first != parent){ edg[child.first] = child.second; v[child.first] = v[node] + child.second; dfs(child.first, node); } } tm[node].second = dfsTime; } namespace AINT{ pii aint[4 * NMAX + 1]; long long lazy[4 * NMAX + 1]; void build(int node, int left, int right){ lazy[node] = 0; if(left == right){ aint[node] = {v[lin[left]], lin[left]}; return; } int mid = (left + right) / 2; build(2 * node, left, mid); build(2 * node + 1, mid + 1, right); aint[node] = max(aint[2 * node], aint[2 * node + 1]); } void propag(int node, int left, int right){ aint[node].first += lazy[node]; if(left < right){ lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } void update(int node, int left, int right, int uleft, int uright, int val){ propag(node, left, right); if(uleft <= left && right <= uright){ lazy[node] += val; propag(node, left, right); return; } int mid = (left + right) / 2; if(uleft <= mid){ update(2 * node, left, mid, uleft, uright, val); } if(mid + 1 <= uright){ update(2 * node + 1, mid + 1, right, uleft, uright, val); } propag(2 * node, left, mid); propag(2 * node + 1, mid + 1, right); aint[node] = max(aint[2 * node], aint[2 * node + 1]); } pii query(int node, int left, int right, int qleft, int qright){ propag(node, left, right); if(qleft <= left && right <= qright){ return aint[node]; } int mid = (left + right) / 2; pii ans = {0, 0}; if(qleft <= mid){ ans = query(2 * node, left, mid, qleft, qright); } if(mid + 1 <= qright){ ans = max(ans, query(2 * node + 1, mid + 1, right, qleft, qright)); } return ans; } } bool used[NMAX + 1]; int n, k; long long solve(int root){ for(int i = 1; i <= n; i++){ used[i] = false; } dfsTime = 0; edg[root] = 0; dfs(root, 0); AINT::build(1, 1, n); long long ans = 0; for(int i = 1; i <= k; i++){ pii x = AINT::query(1, 1, n, 1, n); int node = x.second; ans += x.first; while(node != 0 && !used[node]){ used[node] = true; AINT::update(1, 1, n, tm[node].first, tm[node].second, -edg[node]); node = par[node]; } } return ans; } signed main(){ cin >> n >> k; for(int i = 1; i <= n - 1; i++){ int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } for(int i = 1; i <= n; i++){ cout << solve(i) << '\n'; } return 0; } /* 11 3 1 2 5 2 3 3 2 6 5 3 4 4 3 5 2 1 7 6 7 8 4 7 9 5 1 10 1 10 11 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...