Submission #151416

#	Time	Username	Problem	Language	Result	Execution time	Memory
151416		flashmt	Harbingers (CEOI09_harbingers)	C++17	100 / 100	153 ms	18424 KiB

harbingers

#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 (stderr)

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]

• Subtask 1: 100 / 100