Submission #232875

#	Time	Username	Problem	Language	Result	Execution time	Memory
232875		AlexLuchianov	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	4992 KiB

beads

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
ll const inf = 1000000000000000000;

vector<pair<int,int>> g[1 + nmax];

ll dp[1 + nmax][2];

void dfs(int node, int parent){
  ll sum = 0;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h].first;
    int cost = g[node][h].second;
    if(to != parent) {
      dfs(to, node);
      sum += max(dp[to][0], dp[to][1] + cost);
    }
  }

  dp[node][0] = sum;
  dp[node][1] = -inf;

  ll smax = -inf;

  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h].first;
    int cost = (g[node][h].second);
    if(to != parent){
      dp[node][0] = max(dp[node][0], sum + smax - max(dp[to][0], dp[to][1] + cost) + dp[to][0] + cost);
      dp[node][1] = max(dp[node][1], sum - max(dp[to][0], dp[to][1] + cost) + dp[to][0] + cost);
      smax = max(smax, - max(dp[to][0], dp[to][1] + cost) + dp[to][0] + cost);
    }
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1;i < n; i++){
    int x, y, cost;
    cin >> x >> y >> cost;
    g[x].push_back({y, cost});
    g[y].push_back({x, cost});
  }
  dfs(1, 0);
  cout << dp[1][0];
  return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
beads.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

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