Submission #1009024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009024		Cookie	Road Closures (APIO21_roads)	C++14	36 / 100	2037 ms	33228 KiB

roads

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
//#define int long long
typedef unsigned long long ull;
//const int x[4] = {0, 0, 1, -1};
//const int y[4] = {1, -1, 0, 0};
const int mxn = 2e5 + 5;
const ll mod = 998244353, mod2 = 1e9 + 1977, inf = 1e17 + 1;
ll dp[mxn + 1][2], n;
int deg[mxn + 1];
vt<pll>adj[mxn + 1];
void dfs(int s, int pre, int need){
    vt<ll>comp;
    ll tot = 0;
    for(auto [i, w]: adj[s]){
        if(i != pre){
            dfs(i, s, need); tot += dp[i][0]; comp.pb(dp[i][1] + w - dp[i][0]);
        }
    }
    sort(ALL(comp));
    int rem = deg[s] - need;
    int id = 0;
    for(;id < sz(comp); id++){
        if(comp[id] > 0)break;
        tot += comp[id];
    }
    if(sz(comp) < rem)dp[s][0] = inf;
    else{
        dp[s][0] = tot;
        for(int i = id; i < rem; i++)dp[s][0] += comp[i];
    }
    
    dp[s][1] = tot;
    for(int i = id; i < rem - 1; i++)dp[s][1] += comp[i];
    //cout << s << " " << dp[s][0] << " " << dp[s][1] << "\n";
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    n = N;
    bool ok = 1;
    for(int i = 0; i < n - 1; i++){
        U[i]++; V[i]++;
        ok &= (U[i] == 1);
        adj[U[i]].pb(mpp(V[i], W[i])); adj[V[i]].pb(mpp(U[i], W[i])); deg[U[i]]++; deg[V[i]]++;
    }
    if(ok){
        sort(ALL(W));
        vt<ll>res; res.pb(0);
        for(int i = 0; i < n - 1; i++){
            res.pb(res.back() + 1LL * W[i]);
        }
        reverse(ALL(res));
        return(res);
    }
    vt<ll>res;
    for(int i = 0; i <= *max_element(deg + 1, deg + n + 1); i++){
        dfs(1, -1, i);
        res.pb(dp[1][0]);
    }
    for(int i = *max_element(deg + 1, deg + n + 1) + 1; i < n; i++){
        res.pb(0);
    }
    return(res);
}
/*
int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> U(N - 1), V(N - 1), W(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
  for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld",closure_costs[i]);
  }
  printf("\n");
  return 0;
}
*/

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [i, w]: adj[s]){
      |              ^

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