oj.uz

Submission #968481

# Submission time Handle Problem Language Result Execution time Memory
968481 2024-04-23T13:19:18 Z noyancanturk Harbingers (CEOI09_harbingers) C++17
40 / 100
 88 ms 35816 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=3e5+100;
const int mod=1e9+7;
    
using pii=pair<int,int>;
    
int a[lim],b[lim];
vector<pii>v[lim];
    
int dep[lim];
int ans[lim];

deque<signed>cur;
    
#define calc(i) (ans[i]-a[node]*dep[i])
    
void dfs(int node,int par){
    if(node==1){
        ans[node]=0;
    }else{
        int l=0,r=cur.size()-1;
        while(l<r){
            int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
            int val1=calc(cur[mid1]),val2=calc(cur[mid2]);
            ans[node]=LLONG_MAX;
            if(val1<val2){
                if(val1<ans[node])ans[node]=val1;
                r=mid2-1;
            }else{
                if(val2<ans[node])ans[node]=val2;
                l=mid1+1;
            }
        }
        ans[node]+=b[node]+a[node]*dep[node];
    }
    vector<int>popped;
    int sz;
    while(1<(sz=cur.size())){
        if(
            (ans[node]-ans[cur[0]])*(dep[cur[1]]-dep[cur[0]])>
            (ans[cur[0]]-ans[cur[1]])*(dep[cur[0]]-dep[node])
        ){
            popped.pb(cur[0]);
            cur.pop_front();
        }else{
            break;
        }
    }
    cur.push_front(node);
    for(auto[j,c]:v[node]){
        if(j^par){
            dep[j]=dep[node]+c;
            dfs(j,node);
        }
    }
    cur.pop_front();
    for(int i:popped){
        cur.push_front(i);
    }
}
    
void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y,z;
        cin>>x>>y>>z;
        v[x].pb({y,z});
        v[y].pb({x,z});
    }
    for(int i=2;i<=n;i++){
        cin>>b[i]>>a[i];
    }
    dfs(1,0);
    for(int i=2;i<=n;i++){
        cout<<ans[i]<<" ";
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 37 ms 22204 KB Output is correct
4 Correct 51 ms 26684 KB Output is correct
5 Correct 67 ms 31280 KB Output is correct
6 Runtime error 81 ms 35816 KB Memory limit exceeded
7 Incorrect 43 ms 21828 KB Output isn't correct
8 Incorrect 88 ms 26392 KB Output isn't correct
9 Incorrect 87 ms 29380 KB Output isn't correct
10 Incorrect 68 ms 27612 KB Output isn't correct