Submission #746042

#	Time	Username	Problem	Language	Result	Execution time	Memory
746042		gun_gan	Road Closures (APIO21_roads)	C++17	24 / 100	725 ms	6872 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e3 + 5;

vector<int> g[N];
ll dp[N][2];

map<pair<int, int>, int> id;  

void dfs(int v, int p, int k, vector<int> &w) {
      for(auto u : g[v]) {
            if(u == p) continue;
            dfs(u, v, k, w);
      }

      priority_queue<pair<ll, ll>> vals;
      for(auto u : g[v]) {
            if(u == p) continue;
            vals.push({dp[u][0] - dp[u][1], dp[u][1]});
      }

      int cnt = 0, cnt2 = 1;
      while(!vals.empty()) {
            auto [x, y] = vals.top(); vals.pop();
            if(x > 0 && cnt + 1 <= k) {
                  dp[v][0] += y;
                  cnt++;
            } else {
                  dp[v][0] += x + y;
            }
            if(x > 0 && cnt2 + 1 <= k) {
                  dp[v][1] += y;
                  cnt2++;
            } else {
                  dp[v][1] += x + y;
            }
      }
      if(v > 0) dp[v][0] += w[id[{v, p}]];
}     

vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
      for(int i = 0; i < n - 1; i++) {
            g[u[i]].push_back(v[i]);
            g[v[i]].push_back(u[i]);
            id[{u[i], v[i]}] = i;
            id[{v[i], u[i]}] = i;
      }

      vector<ll> res;
      for(int k = 0; k <= n - 1; k++) {
            for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = 0;
            dfs(0, -1, k, w);     
            res.push_back(dp[0][0]);
      }

      return res;
}

// int main() {
//       auto r = minimum_closure_costs(4, {0, 1, 2}, {1, 2, 3}, {1, 1000000000, 2});
//       for(auto x : r) cout << x << " "; cout << '\n';
// }

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