oj.uz

답안 #973667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973667 2024-05-02T09:17:07 Z duckindog Harbingers (CEOI09_harbingers) C++17
70 / 100
 1000 ms 24576 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 1;
int n;
vector<pair<int, int>> ad[N];
int s[N], velocity[N];
int d[N];

struct Line { 
  long long a, b;
  double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
};
struct CHT { 
  vector<Line> hull;
  vector<pair<int, Line>> save;

  CHT() { hull.push_back({0, 0}); }

  void add(Line line) { 
    while (hull.size() > 1 && hull.end()[-2].x(hull.end()[-1]) >= hull.end()[-2].x(line)) { 
      save.push_back({1, hull.end()[-1]});
      hull.pop_back();
    }
    save.push_back({-1, line});
    hull.push_back(line);
  }
  long long query(int u) { 
    auto cal = [&](int it) { 
      return hull[it].a * velocity[u] + hull[it].b + 1ll * d[u] * velocity[u] + s[u];
    };
    int l = 0, r = hull.size() - 2, it = 0;
    while (l <= r) { 
      int mid = l + r >> 1;
      if (cal(mid) >= cal(mid + 1)) l = it = mid + 1;
      else r = mid - 1;
    }
    return cal(it);
  }
} convex;

long long dp[N];
void dfs(int u, int p = 0) {  
  auto& ret = dp[u];
  ret = min(ret, convex.query(u));
  convex.add({-d[u], ret});
  
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    d[v] = d[u] + w;
    dfs(v, u);
  }

  convex.hull.pop_back();
  convex.save.pop_back();
  while (convex.save.size()) { 
    const auto& [t, line] = convex.save.end()[-1];
    if (t == -1) break;
    else convex.hull.push_back(line);
    convex.save.pop_back();
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 2; i <= n; ++i) { 
    int u, v, w; cin >> u >> v >> w;
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
  for (int i = 2; i <= n; ++i) cin >> s[i] >> velocity[i];

  memset(dp, 40, sizeof dp);
  dfs(1);

  for (int i = 2; i <= n; ++i) cout << dp[i] << " \n"[i == n];
}

Compilation message

harbingers.cpp:13:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   13 |   double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
      |                  ^~~~
harbingers.cpp: In member function 'long long int CHT::query(int)':
harbingers.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |       int mid = l + r >> 1;
      |                 ~~^~~

Subtask #1
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 3 ms 5284 KB Output is correct
3 Correct 32 ms 14020 KB Output is correct
4 Correct 44 ms 17120 KB Output is correct
5 Correct 52 ms 21448 KB Output is correct
6 Correct 69 ms 24576 KB Output is correct
7 Correct 48 ms 11976 KB Output is correct
8 Execution timed out 1022 ms 17484 KB Time limit exceeded
9 Execution timed out 1041 ms 13452 KB Time limit exceeded
10 Execution timed out 1062 ms 17700 KB Time limit exceeded