oj.uz

Submission #968488

# Submission time Handle Problem Language Result Execution time Memory
968488 2024-04-23T13:36:04 Z noyancanturk Harbingers (CEOI09_harbingers) C++17
60 / 100
 1000 ms 36024 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;
            ans[node]=calc(cur[0]);
            while(l<=r){
                int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
                int val1=calc(cur[mid1]),val2=calc(cur[mid2]);
                //cerr<<ans[node]<<" "<<val1<<" "<<val2<<"\n";
                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.size()-1;0<=i;i--){
            cur.push_front(popped[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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 43 ms 22168 KB Output is correct
4 Correct 53 ms 26708 KB Output is correct
5 Correct 69 ms 31268 KB Output is correct
6 Runtime error 97 ms 36024 KB Memory limit exceeded
7 Correct 43 ms 21840 KB Output is correct
8 Execution timed out 1063 ms 26220 KB Time limit exceeded
9 Execution timed out 1061 ms 22832 KB Time limit exceeded
10 Execution timed out 1039 ms 27244 KB Time limit exceeded