제출 #973560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973560		duckindog	Harbingers (CEOI09_harbingers)	C++17	40 / 100	114 ms	32940 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

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

int sz[N], d[N];
void dfs(int u, int p = -1) { 
  for (const auto& [v , w] : ad[u]) { 
    if (v == p) continue;
    d[v] = d[u] + w;
    dfs(v, u);
    sz[u] += sz[v] + 1;
  }
}

int head[N], par[N], st[N], ed[N], rvs[N], it;
void hld(int u, int p = -1) { 
  st[u] = ++it; rvs[it] = u;
  
  sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
    return sz[a.first] > sz[b.first];
  });
  
  bool heavy = false;
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    par[v] = u;
    if (!heavy) head[v] = head[u], heavy = true, hld(v, u);
    else head[v] = v, hld(v, u);
  }

  ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
vector<int> get(int u) { 
  vector<int> ret;
  while (head[u] != 1) { 
    ret.push_back(head[u]);
    u = par[head[u]];
  }
  ret.push_back(1);
  return ret;
}


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;

  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))
      hull.pop_back();
    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[N];

long long dp[N];
void dfs1(int u, int p = 0) {  
  auto& ret = dp[u];
  for (const auto& x : get(u)) ret = min(ret, convex[x].query(u));
  convex[head[u]].add({-1ll * d[u], ret});

  sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
    return sz[a.first] < sz[b.first];
  });
  
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    dfs1(v, u);
  }
}

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];

  dfs(1); hld(head[1] = par[1] = 1);
  
  memset(dp, 40, sizeof dp);
  dfs1(1);

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

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp:52:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   52 |   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:70:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 40 / 100