Submission #394917

#	Time	Username	Problem	Language	Result	Execution time	Memory
394917		radaiosm7	Harbingers (CEOI09_harbingers)	C++98	0 / 100	179 ms	65540 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
int n, i, j, u1, v1, lo, ri, mid, cc;
long long w;
long long dp[100005];
long long dist[100005];
long long v[100005];
long long m[100005];
deque<int> q;
pair<long long, long long> lines[100005];
double slope(int i, int j) { return (double)(lines[j].second - lines[i].second) / (lines[i].first - lines[j].second); }
vector<pair<int, long long> > adj[100005];

void dfs(int x, int p=-1) {
  if (x > 1) {
    lo = 0;
    ri = q.size()-1;

    while (lo < ri) {
      mid = (lo+ri)/2;
      if (lines[q[mid]].first*v[x]+dp[q[mid]] <= lines[q[mid+1]].first*v[x]+dp[q[mid+1]]) {
        lo = mid+1;
      }
      else {
        ri = mid;
      }
    }

    dp[x] = m[x] + v[x]*dist[x] + lines[q[mid]].first*v[x] + lines[q[mid]].second;
    lines[cc].first = -dist[x];
    lines[cc].second = dp[x];
  }


  stack<int> thrown;
  while (q.size() > 1 && slope(q[q.size() - 2], q.back()) >= slope(q.back(), cc)) {
    thrown.push(q.back());
    q.pop_back();
  }
  q.push_back(cc++);

  for (auto y : adj[x]) {
    if (y.first != p) {
      dist[y.first] = dist[x]+y.second;
      dfs(y.first, x);
    }
  }

  q.pop_back();
  while (!thrown.empty()) {
    q.push_back(thrown.top());
    thrown.pop();
  }
  return;
}

int main() {
  scanf("%d", &n);

  for (i=0; i < n-1; ++i) {
    scanf("%d%d%lld", &u1, &v1, &w);
    adj[u1].push_back(make_pair(v1,w));
    adj[v1].push_back(make_pair(u1,w));
  }

  for (i=2; i <= n; ++i) {
    scanf("%lld%lld", &m[i], &v[i]);
  }

  cc = 0;
  dp[1] = 0LL;
  dist[1] = 0LL;
  dfs(1);

  for (i=2; i <= n; ++i) {
    printf("%lld%c", dp[i], (i==n)?'\n':' ');
  }
  return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
harbingers.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d%d%lld", &u1, &v1, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%lld%lld", &m[i], &v[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100