Submission #883280

#	Time	Username	Problem	Language	Result	Execution time	Memory
883280		nguyentunglam	Beads and wires (APIO14_beads)	C++17	100 / 100	115 ms	26096 KiB

beads

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 2e5 + 10;

int f[N], g[N], h[N];

int _f[N], _g[N], _h[N];

int maxw[2][N];

vector<pair<int, int> > adj[N];

void dfs(int u, int p) {
  maxw[0][u] = maxw[1][u] = -1e9;
  for(auto &[v, w] : adj[u]) if (v != p) {
    dfs(v, u);
    h[v] = max(f[v], g[v] + w);
    f[u] += h[v];
    maxw[1][u] = max(maxw[1][u], w + f[v] - h[v]);
    if (maxw[0][u] < maxw[1][u]) swap(maxw[0][u], maxw[1][u]);
  }
  g[u] = f[u] + maxw[0][u];
}

void _dfs(int u, int p, int w, int pre_cost) {
  if (p) {
    _f[u] = f[p] - h[u] + _h[p];
    int cost = maxw[0][p];
    if (w + f[u] - h[u] == cost) cost = maxw[1][p];
    cost = max(cost, pre_cost);
    _g[u] = _f[u] + cost;
    _h[u] = max(_f[u], _g[u] + w);
    int new_cost = w + _f[u] - _h[u];
    pre_cost = new_cost;
  }

  for(auto &[v, next_w] : adj[u]) if (v != p) {
    _dfs(v, u, next_w, pre_cost);
  }
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  int n; cin >> n;

  for(int i = 1; i < n; i++) {
    int a, b, c; cin >> a >> b >> c;
    adj[a].emplace_back(b, c);
    adj[b].emplace_back(a, c);
  }

  dfs(1, 0);

  _dfs(1, 0, 0, -1e9);

  int ans = 0;

  for(int i = 1; i <= n; i++) {
    ans = max(ans, f[i] + _h[i]);
  }

  cout << ans;
}

Compilation message (stderr)

beads.cpp: In function 'int32_t main()':
beads.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:56:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:57:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43