Submission #41620

#	Time	Username	Problem	Language	Result	Execution time	Memory
41620		funcsr	Beads and wires (APIO14_beads)	C++14	100 / 100	396 ms	28648 KiB

beads

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;
#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define _1 first
#define _2 second
#define pb push_back
//#define INF 2100000000
#define INF (1LL<<40)

int N;
vector<P> G[200000];
P dp[200000][3];
void update(int x, int v, int s) {
  if (P(v, s) > dp[x][1]) dp[x][2] = dp[x][1], dp[x][1] = P(v, s);
  else if (P(v, s) > dp[x][2]) dp[x][2] = P(v, s);
}
int get(int x, int s=-2) { return dp[x][1+(dp[x][1]._2==s)]._1; }

void dfs(int x, int p) {
  dp[x][0] = P(0, -1);
  dp[x][1] = P(-INF, -1);
  dp[x][2] = P(-INF, -1);
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, len = pp._2;
    dfs(t, x);
    int v = max(dp[t][0]._1, dp[t][1]._1+len);
    dp[x][0]._1 += v;
  }
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, len = pp._2;
    int v = max(dp[t][0]._1, dp[t][1]._1+len);
    update(x, dp[x][0]._1-v + dp[t][0]._1+len, t);
  }
}

void dfs2(int x, int p, int plen, int diff) {
  if (p != -1) {
    int pv = max(plen + get(p, x) - diff, dp[p][0]._1 - diff);
    for (int k=1; k<=2; k++) if (dp[x][k]._1 != -INF) dp[x][k]._1 += pv;
    update(x, dp[x][0]._1 + plen + dp[p][0]._1 - diff, p);
    int old =dp[x][0]._1;
    dp[x][0]._1 += pv;
  }
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, len = pp._2;
    dfs2(t, x, len, max(dp[t][0]._1, dp[t][1]._1+len));
  }
}

signed main() {
  cin >> N;
  rep(i, N-1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].pb(P(b, c));
    G[b].pb(P(a, c));
  }
  dfs(0, -1);
  dfs2(0, -1, 0, 0);
  int m = 0;
  rep(i, N) m = max(m, dp[i][0]._1);
  cout << m << "\n";
  return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs2(long long int, long long int, long long int, long long int)':
beads.cpp:50:9: warning: unused variable 'old' [-Wunused-variable]
     int old =dp[x][0]._1;
         ^~~

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