Submission #234665

#	Time	Username	Problem	Language	Result	Execution time	Memory
234665		AlexLuchianov	Beads and wires (APIO14_beads)	C++14	100 / 100	273 ms	31208 KiB

beads

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

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;
int const inf = 1000000000;

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

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

ll maxrange(vector<pair<ll,int>> &temp, int avoid){
  for(int i = 0; i < temp.size(); i++)
    if(temp[i].second != avoid)
      return temp[i].first;
  return 0;
}

void dfs2(int node, int parent, int up){
  dp2[node][1] = max(dp2[node][0], dp2[node][1]);

  ll sum = dp2[node][1];
  vector<pair<ll,int>> temp;
  temp.push_back({-dp2[node][1] + dp2[node][0] + up, parent});
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h].first;
    sum += dp[to][1];
    temp.push_back({-dp[to][1] + dp[to][0] + g[node][h].second, to});
  }
  sort(temp.begin(), temp.end());
  reverse(temp.begin(), temp.end());

  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h].first;
    dp2[to][0] = sum - dp[to][1];
    dp2[to][1] = dp2[to][0] + maxrange(temp, to) + g[node][h].second;
  }
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h].first;
    int cost = g[node][h].second;
    dfs2(to, node, 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, 0);
  dp2[1][1] = 0;
  dfs2(1, 0, -inf);
  ll result = 0;
  for(int i = 1;i <= n; i++)
    result = max(result, dp[i][0] + dp2[i][1]);
  cout << result;
  return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
beads.cpp:27: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++){
                  ~~^~~~~~~~~~~~~~~~
beads.cpp: In function 'll maxrange(std::vector<std::pair<long long int, int> >&, int)':
beads.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int, int)':
beads.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
beads.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
beads.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

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