Submission #558825

#	Time	Username	Problem	Language	Result	Execution time	Memory
558825		hoanghq2004	Road Closures (APIO21_roads)	C++14	31 / 100	2087 ms	35844 KiB

roads

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "roads.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, k;
long long f[N][2];
vector <pair <int, int> > g[N];

vector <int> s[N];
int vis[N], ti;

inline void dfs(int u, int p) {
    vis[u] = ti;
    f[u][0] = f[u][1] = 0;
    for (auto [v, w]: g[u])
        if (v != p && g[v].size() > k) dfs(v, u);
    vector <long long> tmp;
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        f[u][0] += f[v][0] + w;
        f[u][1] += f[v][0] + w;
        tmp.push_back(- f[v][1] + f[v][0] + w);
    }
    if (k) {
        sort(tmp.begin(), tmp.end(), greater<>());
        for (int j = 0; j < k && j < tmp.size() && tmp[j] > 0; ++j)
            f[u][0] -= tmp[j];
        for (int j = 0; j < k - 1 && j < tmp.size() && tmp[j] > 0; ++j)
            f[u][1] -= tmp[j];
    }
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    n = N;
    for (int i = 0; i < N - 1; ++i) {
        int u = U[i], v = V[i], w = W[i];
        ++u, ++v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for (int i = 1; i <= n; ++i) s[g[i].size()].push_back(i);
    set <int> rem;
    for (int i = 1; i <= n; ++i) rem.insert(i);
    vector <long long> ans;
    for (k = 0; k < n; ++k) {
        ++ti;
        long long cost = 0;
        for (auto u: s[k]) rem.erase(u), f[u][0] = f[u][1] = 0;
        for (auto u: rem) if (vis[u] != ti) dfs(u, 0), cost += f[u][0];
        ans.push_back(cost);
    }
    return ans;
}


//int main() {
//    freopen("test.inp", "r", stdin);
//  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)':
roads.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for (auto [v, w]: g[u])
      |               ^
roads.cpp:27:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |         if (v != p && g[v].size() > k) dfs(v, u);
      |                       ~~~~~~~~~~~~^~~
roads.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for (auto [v, w]: g[u]) {
      |               ^
roads.cpp:37:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j = 0; j < k && j < tmp.size() && tmp[j] > 0; ++j)
      |                                  ~~^~~~~~~~~~~~
roads.cpp:39:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int j = 0; j < k - 1 && j < tmp.size() && tmp[j] > 0; ++j)
      |                                      ~~^~~~~~~~~~~~

• Subtask 1: 0 / 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