Submission #979958

#	Time	Username	Problem	Language	Result	Execution time	Memory
979958		nnin	Road Closures (APIO21_roads)	C++14	0 / 100	2087 ms	15208 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
using ll = long long;
  
int done[100005], vis[100005];
int ct[100005];
vector<int> deg[100005], W;
vector<pii> adj[100005];
ll dp[100005][2]; //0 cut par, 1 cut child
int addidx[100005];

void dfs(int u, int p, int mx) {
  vis[u] = 1;
  dp[u][0] = dp[u][1] = 0;
  bool one = 0;
  for(auto [v, i]:adj[u]) {
    int w = W[i];
    if(v==p || ct[v]<=mx || done[i]) continue;
    dfs(v, u, mx);
    dp[u][0] += min(dp[v][0]+w, dp[v][1]);
    dp[u][1] += min(dp[v][0]+w, dp[v][1]);
    if(dp[v][0]+w<dp[v][1]) one = 1;
  }
  addidx[u] = -1;
  if(!one) {
    ll add = 1e18;
    for(auto [v, i]:adj[u]) {
      int w = W[i];
      if(v==p || ct[v]<=mx || done[i]) continue;
      ll val = min(dp[v][0], dp[v][1])+w-dp[v][1];
      if(val<add) {
        add = val;
        addidx[u] = i;
      }
    }
    if(add==1e18) {
      for(auto [v, i]:adj[u]) {
        int w = W[i];
        if(v==p || done[i]) continue;
        ll val = min(dp[v][0], dp[v][1])+w-dp[v][1];
        if(w<add) {
          add = val;
          addidx[u] = i;
        }
      }
    }
    dp[u][1] += add;
  }
}

void dfsback(int u, int p, int mx, int j) {
  for(auto [v, i]:adj[u]) {
    int w = W[i];
    if(j==1 && addidx[u]==i) {
      done[i] = 2;
      dfsback(v, u, mx, (dp[v][0]<=dp[v][1] ? 0:1));
      continue;
    }
    if(v==p || ct[v]<=mx || done[i]) continue;
    if(dp[v][0]+w<=dp[v][1]) {
      done[i] = 2;
      dfsback(v, u, mx, 0);
    } else {
      dfsback(v, u, mx, 1);
    }
  }
}

vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> ww) {
  W = ww;
  for(int i=0;i<n-1;i++) {
    ct[U[i]]++;
    ct[V[i]]++;
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  for(int i=0;i<n;i++) {
    deg[ct[i]].push_back(i);
  }
  vector<long long> ans(n, 0);
  for(int i=n-1;i>=0;i--) {
    for(int j=0;j<n;j++) vis[j] = 0;
    if(i<n-1) ans[i] = ans[i+1];
    for(int u=0;u<n;u++) {
      if(ct[u]<=i || vis[u]) continue;
      dfs(u, -1, i);
      ans[i] += dp[u][1];
      dfsback(u, -1, i, 1);
    }
    for(int j=0;j<n-1;j++) {
      if(done[j]==2) {
        done[j] = 1;
        ct[U[j]]--;
        ct[V[j]]--;
      }
    }
  }
  return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:20:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |   for(auto [v, i]:adj[u]) {
      |            ^
roads.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [v, i]:adj[u]) {
      |              ^
roads.cpp:41:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |       for(auto [v, i]:adj[u]) {
      |                ^
roads.cpp: In function 'void dfsback(int, int, int, int)':
roads.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |   for(auto [v, i]:adj[u]) {
      |            ^

• 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