# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
337037 | Vince729 | Harbingers (CEOI09_harbingers) | C++11 | 1084 ms | 24024 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<complex>
#include<cassert>
#include<stack>
using namespace std;
typedef long long ll;
typedef complex<double> pt;
typedef pair<ll, ll> pii;
#define x() real()
#define y() imag()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define in(mp, v) (mp.find(v) != mp.end())
const int MAXN = 100005;
const int MOD = 1000000007;
class cht {
private:
vector<long long> m, b;
int sz = 0;
bool test(int i, int j, int k) {
return (b[j]-b[i])*(m[k]-m[i]) > (b[k]-b[i])*(m[k]-m[i]);
}
long long eval(int i, long long x) {
return m[i]*x+b[i];
}
public:
int insert(long long mv, long long bv) {
sz++;
m.push_back(mv); b.push_back(bv);
int rem = 0;
while (sz >= 3 && !test(sz-3, sz-2, sz-1)) {
swap(m[sz-1], m[sz-2]);
swap(b[sz-1], b[sz-2]);
sz--;
rem++;
}
return rem;
}
long long query(long long x) {
int l = 0, r = sz-2;
while (l <= r) {
int mid = (l+r)/2;
if (eval(mid, x) > eval(mid+1, x)) {
l = mid+1;
} else {
r = mid-1;
}
}
return eval(l, x);
}
void rest(int cnt) {
m.erase(m.end()-cnt-1);
b.erase(b.end()-cnt-1);
sz += cnt-1;
}
void popLast() {
m.pop_back();
b.pop_back();
sz--;
}
};
int n;
vector<pair<int, ll>> adj[MAXN];
ll si[MAXN], vi[MAXN];
cht ch;
ll ans[MAXN];
void dfs(int x, int p, ll d) {
if (x != 1) ans[x] = ch.query(vi[x])+d*vi[x]+si[x];
int rem = ch.insert(-d, ans[x]);
for (auto pv : adj[x]) {
if (pv.first != p) {
dfs(pv.first, x, d+pv.second);
}
}
ch.rest(rem);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n-1; i++) {
int u, v; ll 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 >> si[i] >> vi[i];
}
dfs(1, 1, 0);
for (int i = 2; i <= n; i++) {
cout << ans[i];
if (i < n) cout << " ";
}
cout << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |