daily pastebin goal
76%
SHARE
TWEET

Untitled

a guest Jan 17th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3.  
  4. #define all(x) begin(x), end(x)
  5. #define rall(x) rbegin(x), rend(x)
  6.  
  7. #define file ""
  8.  
  9. using namespace std;
  10. using ll = long long;
  11. using ull = unsigned long long;
  12. using str = string;
  13. using srt = short;
  14.  
  15. const int INF = (int)1e9 + 4;
  16. const int MOD = (int)1e9 + 7;
  17. const int N = 1005;
  18. const ll inf = (ll)4e18;
  19. const ll mod = 998244353;
  20.  
  21. vector<vector<int>> graf;
  22. vector<int> edgesDown;
  23.  
  24. struct edge
  25. {
  26.     int a, b, cost;
  27. };
  28.  
  29. void dfs(int v, int p = -1)
  30. {
  31.     for (auto to : graf[v])
  32.     {
  33.         if (to != p)
  34.         {
  35.             dfs(to, v);
  36.         }
  37.     }
  38.     for (auto to : graf[v])
  39.     {
  40.         edgesDown[v] += edgesDown[to] + 1;
  41.     }
  42.     edgesDown[v]--;
  43. }
  44.  
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
  48.  
  49.     int n, canChange, newDist;
  50.     cin >> n >> canChange >> newDist;
  51.     graf.resize(n);
  52.     edgesDown.resize(n);
  53.     vector<edge> edges(n - 1);
  54.     for (auto &it : edges)
  55.     {
  56.         cin >> it.a >> it.b >> it.cost;
  57.         it.a--; it.b--;
  58.         graf[it.a].push_back(it.b);
  59.         graf[it.b].push_back(it.a);
  60.     }
  61.     ll ans = 0;
  62.     dfs(0);
  63.     edgesDown[0]++;
  64.     for (auto &it : edges)
  65.     {
  66.         if (edgesDown[it.a] < edgesDown[it.b])
  67.         {
  68.             swap(it.a, it.b);
  69.         }
  70.         ans += 1LL * it.cost * (edgesDown[it.b] + 1);
  71.     }
  72.     vector<pair<ll, int>> delts;
  73.     for (int i = 0; i < n - 1; ++i)
  74.     {
  75.         if (edges[i].cost < newDist)
  76.         {
  77.             delts.emplace_back(1LL * (newDist - edges[i].cost) * (edgesDown[edges[i].b] + 1), i);
  78.         }
  79.     }
  80.     sort(rall(delts));
  81.     int wasChanged = min(canChange, (int)delts.size());
  82.     for (int i = 0; i < wasChanged; ++i)
  83.     {
  84.         ans += 1LL * delts[i].first;
  85.     }
  86.     cout << ans << ' ' << wasChanged << endl;
  87.     for (int i = 0; i < wasChanged; ++i)
  88.     {
  89.         cout << delts[i].second + 1 << ' ';
  90.     }
  91.     cout << endl;
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top