Submission #400928

#	Time	Username	Problem	Language	Result	Execution time	Memory
400928		radaiosm7	Harbingers (CEOI09_harbingers)	C++98	0 / 100	3 ms	2636 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, i, u, v;
long long w;
vector<pair<int, long long> > adj[100005];
long long dp[100005];
long long dist[100005];
int up[100005][17];
pair<long long, long long> harbringer[100005];
pair<long long, long long> lines[100005];

double intersect(pair<long long, long long> a, pair<long long, long long> b) {
  return double(b.Y-a.Y) / (a.X-b.X);
}

long long eval(int indx, long long x) {
  return lines[indx].X*x + lines[indx].Y;
}

void dfs(int x, int p=1) {
  int par;
  if (x > 1) {
    par = p;

    for (int j=16; j >= 0; --j) {
      if (eval(up[par][j], harbringer[x].X) < eval(par, harbringer[x].X)) {
        par = up[par][j];
      }
    }

    dp[x] = harbringer[x].Y+dist[x]*harbringer[x].X+eval(par, harbringer[x].X);
  }

  lines[x].X = -dist[x];
  lines[x].Y = dp[x];

  par = p;

  for (int j=16; j >= 0; --j) {
    if (intersect(lines[x], lines[1]) < intersect(lines[1], lines[up[par][j]])) {
      par = up[up[par][j]][0];
    }
  }

  up[x][0] = par;
  for (int j=1; j < 17; ++j) {
    up[x][j] = up[up[x][j-1]][j-1];
  }

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

int main() {
  freopen("test.in", "r", stdin);
  scanf("%d", &n);

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

  for (i=2; i <= n; ++i) {
    scanf("%lld%lld", &harbringer[i].Y, &harbringer[i].X);
  }

  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:61:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   freopen("test.in", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
harbingers.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d%d%lld", &u, &v, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |     scanf("%lld%lld", &harbringer[i].Y, &harbringer[i].X);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100