Submission #725302

#	Time	Username	Problem	Language	Result	Execution time	Memory
725302		quiet_space	Beads and wires (APIO14_beads)	C++14	100 / 100	193 ms	51924 KiB

beads

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
const int maxn = 200005;
int tot_edge, head[maxn], to[maxn<<1], link[maxn<<1], cost[maxn<<1];
inline void add_edge (int x, int y, int c) {
  to[++tot_edge] = y;
  cost[tot_edge] = c;
  link[tot_edge] = head[x];
  head[x] = tot_edge;
}
int fa[maxn], len[maxn], f[maxn][2];
std::vector <int> v[maxn], dp[maxn][2], mx[maxn];
void dfs (int x, int Fa=0) {
  f[x][1] = -1 << 30;
  int mx1 = -1 << 30, mx2 = -1 << 30;
  for(int now=head[x]; now; now=link[now]) {
    if(to[now] == Fa) continue;
    fa[to[now]] = x;
    len[to[now]] = cost[now];
    v[x].push_back (to[now]);
    dfs (to[now], x);
    f[x][0] += std::max(f[to[now]][0], f[to[now]][1] + cost[now]);
    int v = f[to[now]][0] + cost[now] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]);
    if(v > mx1) mx2 = mx1, mx1 = v;
    else if(v > mx2) mx2 = v;
  }
  f[x][1] = f[x][0] + mx1;
  for(int now=head[x]; now; now=link[now]) {
    if(to[now] == Fa) continue;
    dp[x][0].push_back (f[x][0] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]));
    if(f[to[now]][0] + cost[now] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]) == mx1)
      dp[x][1].push_back (dp[x][0].back() + mx2), mx[x].push_back (mx2);
    else
      dp[x][1].push_back (dp[x][0].back() + mx1), mx[x].push_back (mx1);
  }
}
int ans;
void solve (int x) {
  int s = v[x].size();
  FOR(i,0,s-1) {
    f[x][0] = dp[x][0][i], f[x][1] = dp[x][1][i];
    if(fa[x]) {
      f[x][0] += std::max(f[fa[x]][0], f[fa[x]][1] + len[x]);
      f[x][1] = f[x][0] + std::max(mx[x][i], f[fa[x]][0] + len[x] - std::max(f[fa[x]][0], f[fa[x]][1] + len[x]));
    }
    ans = std::max(ans, f[v[x][i]][0] + std::max(f[x][0], f[x][1] + len[v[x][i]]));
    solve (v[x][i]);
  }
}
int main (void) {
  int n = read();
  FOR(i,2,n) {
    int x = read(), y = read(), c = read();
    add_edge (x, y, c);
    add_edge (y, x, c);
  }
  dfs (1); solve (1);
  printf("%d\n", ans);
  return 0;
}

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