# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1028970 | borisAngelov | Harbingers (CEOI09_harbingers) | C++17 | 1046 ms | 32084 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 StackElement
{
Line rem;
double from;
int removedBy;
};
struct ConvexHullTrick
{
vector<pair<Line, double>> lowerEnvelope;
stack<StackElement> removedLines;
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)
{
while (lowerEnvelope.size() >= 1 && toRemove(newLine, lowerEnvelope.back()) == true)
{
removedLines.push({lowerEnvelope.back().first, lowerEnvelope.back().second, newLine.node});
lowerEnvelope.pop_back();
}
if (lowerEnvelope.empty())
{
lowerEnvelope.push_back({newLine, -inf});
}
else
{
lowerEnvelope.push_back({newLine, cross(newLine, lowerEnvelope.back().first)});
}
}
long long query(long long x)
{
if (lowerEnvelope.empty()) return inf;
int l = 0;
int r = lowerEnvelope.size() - 1;
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()
{
Line last = lowerEnvelope.back().first;
lowerEnvelope.pop_back();
while (!removedLines.empty() && removedLines.top().removedBy == last.node)
{
lowerEnvelope.push_back({removedLines.top().rem, removedLines.top().from});
removedLines.pop();
}
}
};
ConvexHullTrick cht;
int a[maxn];
int 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... |