# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1029032 | borisAngelov | Harbingers (CEOI09_harbingers) | C++17 | 69 ms | 18260 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const long long inf = (1LL << 62);
int n;
vector<pair<int, int>> g[maxn];
struct Line
{
long long a;
long long b;
int node;
long long calc(long long x)
{
return a * x + b;
}
};
struct ConvexHullTrick
{
int sz = 0;
int ptr = 0;
pair<Line, double> lowerEnvelope[maxn];
stack<pair<int, int>> rollback;
double cross(const Line& l1, const Line& l2)
{
return (1.0 * (l1.b - l2.b)) / (1.0 * (l2.a - l1.a));
}
bool toRemove(const Line& newLine, pair<Line, double> last)
{
if (newLine.a == last.first.a)
{
return newLine.b <= last.first.b;
}
return cross(newLine, last.first) <= last.second;
}
void addLine(Line newLine)
{
pair<int, int> roll = {ptr, sz + 1};
while (ptr >= 1 && toRemove(newLine, lowerEnvelope[ptr]) == true)
{
--ptr;
}
++sz;
lowerEnvelope[sz] = {newLine, -inf};
if (ptr >= 1)
{
lowerEnvelope[sz].second = cross(lowerEnvelope[sz].first, lowerEnvelope[ptr].first);
}
++ptr;
swap(lowerEnvelope[sz], lowerEnvelope[ptr]);
}
long long query(long long x)
{
if (sz == 0) return inf;
int l = 1;
int r = ptr;
while (l <= r)
{
int mid = (l + r) / 2;
if (lowerEnvelope[mid].second <= 1.0 * x)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return lowerEnvelope[r].first.calc(x);
}
void removeLast()
{
if (rollback.empty()) return;
pair<int, int> roll = rollback.top();
rollback.pop();
swap(lowerEnvelope[ptr], lowerEnvelope[roll.second]);
ptr = roll.first;
--sz;
}
};
ConvexHullTrick cht;
long long a[maxn];
long long b[maxn];
long long dp[maxn];
void dfs(int node, int par, long long dist)
{
if (node == 1)
{
dp[node] = 0;
}
else
{
dp[node] = a[node] + b[node] * dist;
dp[node] = min(dp[node], a[node] + dist * b[node] + cht.query(b[node]));
cht.addLine({-dist, dp[node], node});
}
for (int i = 0; i < g[node].size(); ++i)
{
int to = g[node][i].first;
int w = g[node][i].second;
if (to != par)
{
dfs(to, node, dist + w);
}
}
cht.removeLast();
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n;
for (int i = 1; i <= n - 1; ++i)
{
int x, y, w;
cin >> x >> y >> w;
g[x].push_back({y, w});
g[y].push_back({x, w});
}
for (int i = 2; i <= n; ++i)
{
cin >> a[i] >> b[i];
}
dfs(1, -1, 0);
for (int i = 2; i <= n; ++i)
{
cout << dp[i] << " ";
}
cout << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |