oj.uz

Submission #933863

# Submission time Handle Problem Language Result Execution time Memory
933863 2024-02-26T12:36:59 Z dosts Harbingers (CEOI09_harbingers) C++17
0 / 100
 78 ms 19536 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+1,M = 2e2+1,inf = 2e18;
 
struct CHT{
    deque<long long> times;
    deque<pair<int, long long>> lines;
    long long intersect(pair<int, long long> a,pair<int, long long> b){
        if(b.first > a.first) swap(a,b);
        if(b.second - a.second < 0) return (b.second - a.second) / (a.first - b.first);
        return (b.second - a.second + (a.first - b.first - 1)) / (a.first - b.first);
    }
    void add(pair<int,long long> x){
        while(lines.size() > 0 && ((x.first == lines.back().first) || (intersect(lines.back(),x) <= times.back()))){
            lines.pop_back();
            times.pop_back();
        }
        if(lines.empty()){
            lines.push_back(x);
            times.push_back(0);
        }
        else{
            times.push_back(intersect(x,lines.back()));
            lines.push_back(x);
        }
    }
    long long query(int x){
        while(lines.size() > 1 && times[1] <= x){
            lines.pop_front();
            times.pop_front();
        }
        assert(lines.size());
        return lines.front().second + (long long)x*lines.front().first;
    }
};
 
vector<pii> edges[N];
vi d(N);
 
void dfs(int node,int p,int dep = 0) {
    d[node] = dep;
    for (auto it : edges[node]) if (it.first != p) dfs(it.first,node,dep+it.second);
}
 
void solve() {
    int n;
    cin >> n;
    vi t(n+1),w(n+1);
    for (int i=1;i<=n-1;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    w[1] = t[1] = 0;
    for (int i=2;i<=n;i++) cin >> w[i] >> t[i];
    dfs(1,1);
    vi order(n+1);
    for (int i=1;i<=n;i++) order[i] = i;
    sort(order.begin()+1,order.end(),[&](int x,int y) {
        return d[x] < d[y];
    });
    vi dp(n+1);
    CHT cht;
    for (int i=1;i<=n;i++) {
        int node = order[i];
        if (node > 1) dp[node] = cht.query(t[node])+w[node]+d[node]*t[node];
        else dp[node] = 0;
        cht.add({-d[node],dp[node]});
    }
    for (int i=2;i<=n;i++) cout << dp[i] << " ";
    cout << '\n';
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6744 KB Output isn't correct
2 Incorrect 4 ms 7004 KB Output isn't correct
3 Incorrect 30 ms 12124 KB Output isn't correct
4 Incorrect 44 ms 14676 KB Output isn't correct
5 Incorrect 55 ms 17252 KB Output isn't correct
6 Incorrect 78 ms 19536 KB Output isn't correct
7 Incorrect 44 ms 13996 KB Output isn't correct
8 Incorrect 64 ms 17868 KB Output isn't correct
9 Incorrect 62 ms 18260 KB Output isn't correct
10 Incorrect 60 ms 17608 KB Output isn't correct