Submission #256799

#	Time	Username	Problem	Language	Result	Execution time	Memory
256799		Nightlight	Beads and wires (APIO14_beads)	C++14	100 / 100	252 ms	27628 KiB

beads

#include <bits/stdc++.h>
#define pii pair<int, int>
#define INF 1000000000000000000
using namespace std;

int N;
long long dp0[200005];//side 
long long dp1[200005];//mid connect to 2 chlid (2 side or 1 side and 1 mid)
long long dp2[200005];//mid connect to 1 parent and 1 child (parent is side and child is mid) 
long long dp3[200005];//mid connect to 1 parent and 1 child (parent can be side or mid, child is side)

vector<pii> adj[200005];

void DFS(int u, int p) {
  int v, w;
  long long bs = -INF, bs2 = -INF, bm = -INF, bm2 = -INF;
  int id_bs = 0, id_bs2 = 0, id_bm = 0, id_bm2 = 0;
  long long cur_side, cur_mid, best = 0, sum = 0, best_md = 0;
  for(pii now : adj[u]) {
    v = now.first, w = now.second;
    if(v == p) continue;
    DFS(v, u);
    dp2[v] += w, dp3[v] += w;

    best = max(dp0[v], dp2[v]);
    sum += best;
    best_md = max(best_md, max(dp1[v], dp3[v]) - best);

    //best if choosen
    cur_side = dp0[v] + w - best;
    if(cur_side > bs) {
      bs2 = bs, id_bs2 = id_bs;
      bs = cur_side;
      id_bs = v;
    }else if(cur_side > bs2) {
      bs2 = cur_side;
      id_bs2 = v;
    }

    cur_mid = dp1[v] + w - best;
    if(cur_mid > bm) {
      bm2 = bm, id_bm2 = id_bm;
      bm = cur_mid;
      id_bm = v;
    }else if(cur_mid > bm2) {
      bm2 = cur_mid;
      id_bm2 = v;
    }
  }
  dp0[u] = sum;
  //if mid connect 2 child
  //1 side 1 mid
  if(id_bs != id_bm) {
    dp1[u] = sum + bs + bm;
  }else {
    dp1[u] = sum + max(bs + bm2, bs2 + bm);
  }
  dp1[u] = max(dp1[u], sum + bs + bs2);
  dp1[u] = max(dp1[u], sum + best_md);

  //if mid connect a parent and 1 red child
  dp2[u] = sum + bs;
  //if mid connect a red parent and a child
  dp3[u] = sum + bm;
//  cout << u << " " << dp0[u] << "\n";
}

int main() {
//  freopen("inp.in", "r", stdin);
//  freopen("out.out", "w", stdout);
  scanf("%d", &N);
  int u, v, w;
//  cout << N << "\n";
  for(int i = 1; i < N; i++) {
    scanf("%d %d %d", &u, &v, &w);
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  DFS(1, 0);
  cout << max(dp0[1], dp1[1]) << "\n";
  cin >> N;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

Compilation message (stderr)

beads.cpp: In function 'void DFS(int, int)':
beads.cpp:17:18: warning: variable 'id_bs2' set but not used [-Wunused-but-set-variable]
   int id_bs = 0, id_bs2 = 0, id_bm = 0, id_bm2 = 0;
                  ^~~~~~
beads.cpp:17:41: warning: variable 'id_bm2' set but not used [-Wunused-but-set-variable]
   int id_bs = 0, id_bs2 = 0, id_bm = 0, id_bm2 = 0;
                                         ^~~~~~
beads.cpp: In function 'int main()':
beads.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
beads.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &u, &v, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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