Submission #1825629

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
     
const int maxn = 2e5;
     
int n, son[maxn][2], len[maxn];
long long ans;
typedef pair<long long, long long> Pair;
vector<Pair> set[maxn];
     
void Combine(vector<Pair> &s, int u, int v) {
  s.clear();
  if (u.empty()) {
    return;
  }
  for (int i = 0, j = 0; i < set[u].size(); ++i) {
    if (len[u] + len[v] + set[u][i].second + set[v][j].first > ans) {
      continue;
    }
    while (j + 1 < set[v].size() &&
           len[u] + len[v] + set[u][i].second + set[v][j + 1].first <= ans) {
      ++j;
    }
    s.push_back(Pair(len[u] + set[u][i].first, len[v] + set[v][j].second));
  }
  int m = s.size();
  for (int i = set[u].size() - 1, j = set[v].size() - 1; i >= 0; --i) {
    if (len[u] + len[v] + set[v][j].second + set[u][i].first > ans) {
      continue;
    }
    while (j > 0 &&
           len[u] + len[v] + set[v][j - 1].second + set[u][i].first <= ans) {
      --j;
    }
    s.push_back(Pair(len[v] + set[v][j].first, len[u] + set[u][i].second));
  }
  inplace_merge(s.begin(), s.begin() + m, s.end());
  m = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (i == 0 || s[i].second < s[i - 1].second) {
      s[m++] = s[i];
    }
  }
  s.resize(m);
}
     
bool Check(void) {
  for (int i = n - 1; i >= 0; --i) {
    if (son[i][0] == -1) {
      set[i] = {Pair(0, 0)};
    } else {
      int &u = son[i][0], &v = son[i][1];
      if (set[u].size() > set[v].size()) {
        swap(u, v);
      }
      Combine(set[i], u, v);
    }
  }
  return set[0].size();
}
     
int main(void) {
  scanf("%d", &n);
  memset(son, -1, sizeof son);
  for (int i = 1; i < n; ++i) {
    int par;
    scanf("%d%d", &par, len + i);
    --par;
    swap(son[par][0], son[par][1]);
    son[par][0] = i;
  }
  long long low = 0, high = (long long)maxn * maxn;
  while (low < high) {
    long long mid = low + high >> 1;
    ans = mid;
    if (Check()) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  printf("%lld\n", low);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void Combine(std::vector<std::pair<long long int, long long int> >&, int, int)’:
./Main.cpp:16:9: error: request for member ‘empty’ in ‘u’, which is of non-class type ‘int’
   if (u.empty()) {
         ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:66:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:70:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &par, len + i);
                                 ^