Submission #151416

# Submission time Handle Problem Language Result Execution time Memory
151416 2019-09-02T19:38:09 Z flashmt Harbingers (CEOI09_harbingers) C++17
100 / 100
153 ms 18424 KB
#include <bits/stdc++.h>
using namespace std;

int n, v[100100], q[100100], l[100100];
vector<pair<int, int>> a[100100];
long long f[100100];

int bs(int v, int hullSize)
{
  int low = 2, high = hullSize, res = 1;
  while (low <= high)
  {
    int mid = (low + high) / 2, j = q[mid], k = q[mid - 1];
    if (f[j] - f[k] < 1LL * (l[j] - l[k]) * v)
    {
      res = j;
      low = mid + 1;
    }
    else high = mid - 1;
  }
  return res;
}

int bss(long long F, int L, int hullSize)
{
  int low = 2, high = hullSize, res = hullSize + 1;
  while (low <= high)
  {
    int mid = (low + high) / 2, j = q[mid], k = q[mid - 1];
    if (1. * (F - f[j]) / (L - l[j]) <= 1. * (f[j] - f[k]) / (l[j] - l[k]))
    {
      res = mid;
      high = mid - 1;
    }
    else low = mid + 1;
  }
  return res;
}

void visit(int x, int par, int curHullSize)
{
  int id, save, newHullSize = curHullSize;
  if (par)
  {
      id = bs(v[x], curHullSize);
      f[x] += f[id] + 1LL * (l[x] - l[id]) * v[x];
      newHullSize = id = bss(f[x], l[x], curHullSize);
      save = q[id];
      q[id] = x;
  }

  for (auto u : a[x])
    if (u.first != par)
    {
       l[u.first] = l[x] + u.second;
       visit(u.first, x, newHullSize);
    }

  if (par)
    q[id] = save;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int x, y, z;
  cin >> n;
  for (int i = 1; i < n; i++)
  {
     cin >> x >> y >> z;
     a[x].push_back({y, z});
     a[y].push_back({x, z});
  }
  for (int i = 2; i <= n; i++)
    cin >> f[i] >> v[i];

  q[1] = 1;
  visit(1, 0, 1);
  for (int i = 2; i <= n; i++)
    cout << f[i] << " \n"[i == n];
}

Compilation message

harbingers.cpp: In function 'void visit(int, int, int)':
harbingers.cpp:60:11: warning: 'save' may be used uninitialized in this function [-Wmaybe-uninitialized]
     q[id] = save;
     ~~~~~~^~~~~~
harbingers.cpp:60:11: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 3064 KB Output is correct
3 Correct 52 ms 9852 KB Output is correct
4 Correct 73 ms 12664 KB Output is correct
5 Correct 95 ms 15780 KB Output is correct
6 Correct 115 ms 18424 KB Output is correct
7 Correct 80 ms 10716 KB Output is correct
8 Correct 153 ms 14680 KB Output is correct
9 Correct 143 ms 16220 KB Output is correct
10 Correct 123 ms 15332 KB Output is correct