Submission #883274

#	Time	Username	Problem	Language	Result	Execution time	Memory
883274		nguyentunglam	Beads and wires (APIO14_beads)	C++17	28 / 100	1061 ms	3416 KiB

beads

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

const int N = 1e5 + 10;

int f[N], g[N];

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

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

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);
  }

  int ans = 0;

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

  cout << ans;
}

Compilation message (stderr)

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

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