Submission #649852

#	Time	Username	Problem	Language	Result	Execution time	Memory
649852		alvinpiter	Harbingers (CEOI09_harbingers)	C++17	40 / 100	192 ms	18348 KiB

harbingers

/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MAXN 100000

struct Line {
  LL m, c;
  Line() {}
  Line(LL m_, LL c_): m(m_), c(c_) {}
};

int N, prepTime[MAXN + 3], pace[MAXN + 3];
vector<pair<int, int> > adj[MAXN + 3];
LL depth[MAXN + 3], dp[MAXN + 3];

Line lineContainer[MAXN + 3];
int lineContainerSize = 0;

// Check whether prevLine is obsolete
bool checkObsolete(Line prevPrevLine, Line prevLine, Line newLine) {
  /*
  prevLine is obsolete if the x-coordinate of intersection between the newLine and the prevLine
  is smaller than the x-coordinate of intersection between the prevPrevLine and prevLine

  x-coordinate of the intersection of newLine and prevLine:
  x = (prevLine.c - newLine.c)/(newLine.m - prevLine.m)

  x-coordinate of the intersection of prevPrevLine and prevLine:
  x = (prevLine.c - prevPrevLine.c)/(prevPrevLine.m - prevLine.m)
  */

  // double x1 = (prevLine.c - newLine.c)/(1.0 * newLine.m - prevLine.m);
  // double x2 = (prevLine.c - prevPrevLine.c)/(1.0 * prevPrevLine.m - prevLine.m);
  // return x1 < x2;

  LL numerator = (prevLine.c - newLine.c) * (prevPrevLine.m - prevLine.m) - (prevLine.c - prevPrevLine.c) * (newLine.m - prevLine.m);
  LL denominator = (newLine.m - prevLine.m) * (prevPrevLine.m - prevLine.m);

  if (numerator == 0) {
    return false;
  } else {
    return (numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0);
  }

  // cout << "newLine and prevLine intersection: " << (1.0 * prevLine.c - newLine.c)/(1.0 * newLine.m - prevLine.m) << endl;
  // cout << "prevPrevLine and prevLine intersection: " << (1.0 * prevLine.c - prevPrevLine.c)/(1.0 * prevPrevLine.m - prevLine.m) << endl;
  // cout << (prevLine.c - newLine.c) * (prevPrevLine.m - prevLine.m) << " " << (prevLine.c - prevPrevLine.c) * (newLine.m - prevLine.m) << endl;

  // return (prevLine.c - newLine.c) * (prevPrevLine.m - prevLine.m) < (prevLine.c - prevPrevLine.c) * (newLine.m - prevLine.m);
}

void dfsDepth(int u, int prev = -1) {
  for (auto [v, d]: adj[u]) {
    if (v != prev) {
      depth[v] = depth[u] + d;
      dfsDepth(v, u);
    }
  }
}

LL eval(Line line, LL x) {
  return line.m * x + line.c;
}

LL query(LL x) {
  int lo = 0, hi = lineContainerSize - 2, mid;
  while (hi >= lo) {
    mid = (lo + hi)/2;
    if (eval(lineContainer[mid], x) > eval(lineContainer[mid + 1], x)) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return eval(lineContainer[lo], x);
}

int findInsertionPosition(Line line) {
  if (lineContainerSize == 0) {
    return 0;
  }

  // Find insert position
  int lo = 1, hi = lineContainerSize - 1, mid;
  while (hi >= lo) {
    mid = (lo + hi)/2;
    if (checkObsolete(lineContainer[mid - 1], lineContainer[mid], line)) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
}

void traverse(int u, int prev = -1) {
  // cout << "\nTraverse " << u << endl;
  // cout << "Lines:\n";
  // for (int i = 0; i < lineContainerSize; i++) {
  //   cout << lineContainer[i].m << " " << lineContainer[i].c << endl;
  // }

  if (u == 1) {
    dp[u] = 0;
  } else {
    dp[u] = prepTime[u] + depth[u] * pace[u] + query(pace[u]);
  }

  // cout << "query: " << pace[u] << " " << query(pace[u]) << endl;
  // cout << "new line: " << -depth[u] << " " << dp[u] << endl;

  Line newLine = Line(-depth[u], dp[u]);

  int insertionPosition = findInsertionPosition(newLine);

  // cout << "insertionPosition: " << insertionPosition << endl;

  int oldLineContainerSize = lineContainerSize;
  Line oldLine;
  if (insertionPosition < oldLineContainerSize) {
    oldLine = lineContainer[insertionPosition];
  }

  lineContainerSize = insertionPosition + 1;
  lineContainer[insertionPosition] = newLine;

  for (auto [v, d]: adj[u]) {
    if (v != prev) {
      traverse(v, u);
    }
  }

  // Reset values
  lineContainerSize = oldLineContainerSize;
  if (insertionPosition < oldLineContainerSize) {
    lineContainer[insertionPosition] = oldLine;
  }
}

int main() {
  cin >> N;
  for (int i = 1; i < N; i++) {
    int u, v, d;
    cin >> u >> v >> d;

    adj[u].push_back({v, d});
    adj[v].push_back({u, d});
  }

  for (int i = 2; i <= N; i++) {
    cin >> prepTime[i] >> pace[i];
  }

  depth[1] = 0;
  dfsDepth(1);

  // cout << "\ndepth:\n";
  // for (int i = 1; i <= N; i++) {
  //   cout << i << " " << depth[i] << endl;
  // }

  traverse(1);

  for (int i = 2; i <= N; i++) {
    if (i > 2) {
      cout << " ";
    }
    cout << dp[i];
  }
  cout << endl;
}

• Subtask 1: 40 / 100