# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
936864 | idiotcomputer | Harbingers (CEOI09_harbingers) | C++11 | 1087 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<int,int>
#define pb push_back
#define sz size
#define f first
#define s second
const int mxN = 1e5;
int start[mxN];
int speed[mxN];
vector<pii> adj[mxN];
ll dp[mxN];
ll dist[mxN];
ll comp(int a, int b){
if (dist[b] < dist[a]) swap(a,b);
return (ll) ceil((double) (dp[b] - dp[a]) / (double) (dist[b] - dist[a]));
}
deque<int> all;
void dfs(int node, int p){
dp[node] = 0;
int r = all.sz()-1;
int l = -1;
int curr;
while (r - l > 1){
curr = (r+l)/2;
// cout << comp(all[curr],all[curr+1]) << "-" << all[curr] << " " << all[curr+1] << '\n';
if (comp(all[curr],all[curr+1]) <= (ll) speed[node]){
l = curr;
} else {
r = curr;
}
}
/* cout << node << " " << r << ": ";
for (int i =0; i < all.sz(); i++){
cout << all[i] << " ";
}
cout << "\n";*/
if (l != r){
dp[node] = dp[all[r]] + (dist[node] - dist[all[r]]) * (ll) speed[node] + (ll) start[node];
}
stack<int> rem;
while (all.sz() > 1 && comp(all[all.sz()-1],all[all.sz()-2]) >= comp(all[all.sz()-1],node)){
// cout << comp(all[all.sz()-1],all[all.sz()-2]) << " " << comp(all[all.sz()-1],node) << "\n";
rem.push(all.back());
all.pop_back();
}
all.push_back(node);
for (pii next : adj[node]){
if (next.f != p){
dist[next.f] = dist[node] + next.s;
dfs(next.f,node);
}
}
all.pop_back();
while (rem.sz()>0){
all.push_back(rem.top());
rem.pop();
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int a,b,d;
for (int i =0; i < n-1; i++){
cin >> a >> b >> d;
a -= 1;
b -= 1;
adj[a].pb({b,d});
adj[b].pb({a,d});
}
start[0] = 0;
speed[0] = 0;
for (int i =1; i < n; i++) cin >> start[i] >> speed[i];
dist[0] = 0;
dfs(0,-1);
for (int i =1; i < n; i++){
cout << dp[i] << " ";
}
cout << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |