Submission #48301

#	Time	Username	Problem	Language	Result	Execution time	Memory
48301		octopuses	Beads and wires (APIO14_beads)	C++17	100 / 100	268 ms	20400 KiB

beads

#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define M (ll)(3e17)

using namespace std;
const int N = 200020;

vector < pair < int, int > > G[N];
int n;
ll A[N], B[N], answer, par[N];

void go(int v, int p = 0)
{
  ll mx1 = -2e9, mx2 = -2e9, child = 0, tot = 0;
  for(int i = 0; i < G[v].size(); ++ i)
  {
    int to = G[v][i].first;
    if(to == p)
    {
      par[v] = G[v][i].second;
      swap(G[v][i], G[v].back());
      G[v].pop_back();
      i --;
      continue;
    }
    go(to, v);
    tot += A[to];
    child ++;
  }
  A[v] = B[v] = tot;
  for(int i = 0; i < G[v].size(); ++ i)
  {
    int to = G[v][i].first;
    if(to == p)
      continue;
    A[v] = max(A[v], tot - A[to] + B[to] + par[v] + G[v][i].second);
  }
}

void dfs(int v, ll a, ll b)
{
  ll tot = a;
  ll mx1, mx2;
  mx1 = b - a + par[v];
  mx2 = -2e9;
  for(int i = 0; i < G[v].size(); ++ i)
  {
    int to = G[v][i].first;
    tot += A[to];
    if(mx1 < B[to] - A[to] + G[v][i].second)
    {
      mx2 = mx1;
      mx1 = B[to] - A[to] + G[v][i].second;
    } else
      if(mx2 < B[to] - A[to] + G[v][i].second)
        mx2 = B[to] - A[to] + G[v][i].second;
  }
  answer = max(answer, tot);
  for(int i = 0; i < G[v].size(); ++ i)
  {
    int to = G[v][i].first;
    ll now = mx1;
    if(now == B[to] - A[to] + G[v][i].second)
      now = mx2;
    dfs(to, max(tot - A[to], now + tot - A[to] + G[v][i].second), tot - A[to]);
  }
}

int main()
{
  scanf("%d", &n);
  for(int i = 1; i < n; ++ i)
  {
    int x, y, val;
    scanf("%d %d %d", &x, &y, &val);
    G[x].push_back({y, val});
    G[y].push_back({x, val});
  }
  par[1] = -2e9;
  go(1);
  dfs(1, 0, 0);
  cout << answer << endl;
}

Compilation message (stderr)

beads.cpp: In function 'void go(int, int)':
beads.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < G[v].size(); ++ i)
                  ~~^~~~~~~~~~~~~
beads.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < G[v].size(); ++ i)
                  ~~^~~~~~~~~~~~~
beads.cpp:17:6: warning: unused variable 'mx1' [-Wunused-variable]
   ll mx1 = -2e9, mx2 = -2e9, child = 0, tot = 0;
      ^~~
beads.cpp:17:18: warning: unused variable 'mx2' [-Wunused-variable]
   ll mx1 = -2e9, mx2 = -2e9, child = 0, tot = 0;
                  ^~~
beads.cpp: In function 'void dfs(int, long long int, long long int)':
beads.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < G[v].size(); ++ i)
                  ~~^~~~~~~~~~~~~
beads.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < G[v].size(); ++ i)
                  ~~^~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
beads.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &x, &y, &val);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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