Submission #654733

#	Time	Username	Problem	Language	Result	Execution time	Memory
654733		Sam_a17	Road Closures (APIO21_roads)	C++14	0 / 100	2085 ms	23092 KiB

roads

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
// const long long inf = 1e18;
const int N = 2e5 + 10;
vector<pair<int, long long>> adj[N];
long long dp[N][2];

void dfs(int node, int parent, int max_deg) {
  int cnt = 0;
  for(auto i: adj[node]) {
    if(i.first == parent) continue;
    dfs(i.first, node, max_deg);
    cnt++;
  }

  if(cnt == 0) {
    dp[node][0] = dp[node][1] = 0;
  } else {
    vector<pair<long long, long long>> diff;
    for(auto i: adj[node]) {
      if(i.first == parent) continue;
      diff.push_back({dp[i.first][1] + i.second - dp[i.first][0], i.first});
    }
    sort(all(diff));
    

    int curr_deg = adj[node].size();
    if(max_deg >= curr_deg) {
      long long to_add = 0; 
      for(int i = 0; i < sz(diff); i++) {
        if(diff[i].first < 0) {
          long long edge = diff[i].first - dp[diff[i].second][1];
          edge += dp[diff[i].second][0];

          //
          to_add += dp[diff[i].second][1] + edge;
        } else {
          to_add += dp[diff[i].second][0];
        }
      }

      dp[node][0] = dp[node][1] = to_add;
    } else {
      {
        int qn = curr_deg - max_deg;
        long long to_add = 0, cr = 0; 
        for(int i = 0; i < sz(diff); i++) {
          if(diff[i].first < 0) {
            long long edge = diff[i].first - dp[diff[i].second][1];
            edge += dp[diff[i].second][0];

            //
            to_add += dp[diff[i].second][1] + edge;
            cr++;
          } else {
            if(cr < qn) {
              to_add += diff[i].first + dp[diff[i].second][0];
              cr++;
            } else{
              to_add += dp[diff[i].second][0];
            }
          }
        }

        assert(cr == qn);
        dp[node][0] = to_add; 
      }

      {
        int qn = curr_deg - max_deg - 1;
        long long to_add = 0, cr = 0; 
        for(int i = 0; i < sz(diff); i++) {
          if(diff[i].first < 0) {
            long long edge = diff[i].first - dp[diff[i].second][1];
            edge += dp[diff[i].second][0];

            //
            to_add += dp[diff[i].second][1] + edge;
            cr++;
          } else {
            if(cr < qn) {
              to_add += diff[i].first + dp[diff[i].second][0];
              cr++;
            } else{
              to_add += dp[diff[i].second][0];
            }
          }
        }

        if(cr == qn) {
          dp[node][1] = to_add; 
          dp[node][0] = max(dp[node][0], to_add);
        }
      }
    }
  }
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  bool flag1 = true, flag2 = true;;
  for(int i = 0; i < N - 1; i++) {
    if(U[i] != 0) {
      flag1 = false;
    }
 
    if(U[i] != i || V[i] != i + 1) {
      flag2 = false;
    }
  }
 
  // if(flag1) {
  //   sort(all(W));
  //   vector<long long> answ(N, 0);
  //   int it = 0;
  //   for(int i = N - 2; i >= 0; i--) {
  //     answ[i] = answ[i + 1] + W[it++];
  //   }
 
  //   return answ;
  // }
 
  // if(flag2) {
  //   vector<long long> answ(N, 0);
  //   for(auto i: W) {
  //     answ[0] += i;
  //   }
 
  //   vector<vector<long long>> dp(N, vector<long long> (2, 0));
  //   dp[0][0] = 0;
  //   dp[0][1] = 0;
  
  //   for(int i = 1; i < N; i++) {
  //     dp[i][0] = min(dp[i - 1][1], dp[i - 1][0]) + W[i - 1];
  //     dp[i][1] = dp[i - 1][0];
  //   }
 
  //   answ[1] = min(dp[N - 1][0], dp[N - 1][1]);
  //   return answ;
  // }

  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]});
  }

  vector<long long> answ(N, 0);
  for(auto i: W) {
    answ[0] += i;
  }

  for(int i = 1; i < N; i++) {
    dfs(0, -1, i);
    answ[i] = dp[0][0];
  }
 
  return answ;
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:103:8: warning: variable 'flag1' set but not used [-Wunused-but-set-variable]
  103 |   bool flag1 = true, flag2 = true;;
      |        ^~~~~
roads.cpp:103:22: warning: variable 'flag2' set but not used [-Wunused-but-set-variable]
  103 |   bool flag1 = true, flag2 = true;;
      |                      ^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22