Submission #1119110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119110		Marko2604	Harbingers (CEOI09_harbingers)	C++98	90 / 100	244 ms	34752 KiB

harbingers

        #include<bits/stdc++.h>
        #define ll long long
        #define MAXN 100003
        using namespace std;
        vector<vector<pair<int,int>>>T(MAXN);
        int s[MAXN], v[MAXN];
        struct line
        {
            int node;
            ll k,n;
        };
        ll eval(ll x, line *l) 
        {
            return l->k*x+l->n;
        }
        ll depth[MAXN];
        void depth_dfs(int node, int p)
        {
            for(auto i:T[node])
            {
                if(i.first!=p)
                {
                    depth[i.first]=(ll)i.second+depth[node];
                    depth_dfs(i.first, node);
                }
            }
        }
        vector<vector<line*>>lichao(262151);
        vector<vector<int>>loc(MAXN);
        vector<ll>xx;
        int sz;
        void make_lichao(int n)
        {
            sz = (1<<((int)ceil(log2(n))));
            for(int i=1;i<=n;i++) xx.push_back(v[i]);
            while(xx.size()<sz) xx.push_back(0);
            sort(xx.begin(),xx.end());
        }
        void add_line(line *ln, int node, int l, int r)
        {
            if(lichao[node].empty())
            {
                lichao[node].push_back(ln);
                loc[ln->node].push_back(node);
                return;
            }
            line *lo = lichao[node].back();
            ll lold = eval(xx[l], lo), rold = eval(xx[r], lo);
            ll lnew = eval(xx[l], ln), rnew = eval(xx[r], ln);
            if(lnew>=lold && rnew>=rold) return;
            if(lnew<=lold && rnew<=rold)
            {
                lichao[node].push_back(ln);
                loc[ln->node].push_back(node);
                return;
            }
            int mid = (l+r)/2;
            ll mold = eval(xx[mid], lo), mnew = eval(xx[mid], ln);
            if(lnew<=lold)
            {
                if(mnew<=mold)
                {
                    lichao[node].push_back(ln);
                    loc[ln->node].push_back(node);
                    add_line(lo, 2*node+1, mid+1, r);
                    return;
                }
                else
                {
                    add_line(ln, 2*node, l, mid);
                    return;
                }
            }
            else
            {
                if(mnew<=mold)
                {
                    lichao[node].push_back(ln);
                    loc[ln->node].push_back(node);
                    add_line(lo, 2*node, l, mid);
                    return;
                }
                else
                {
                    add_line(ln, 2*node+1, mid+1, r);
                    return;
                }
            }
            return;
        }
        void pop_line(line l)
        {
            while(!loc[l.node].empty())
            {
                lichao[loc[l.node].back()].pop_back();
                loc[l.node].pop_back();
            }
            return;
        }
        ll get_val(ll x)
        {
            ll res = 100000000000000000;
            int l=0, r=sz-1, node=1;
            while(l<=r)
            {
                if(!lichao[node].empty()) res=min(res, eval(x, lichao[node].back()));
                int mid=(l+r)/2;
                if(xx[mid]<=x) 
                {
                    l=mid+1;
                    node=node*2+1;
                }
                else 
                {
                    r=mid-1;
                    node=node*2;
                }
            }
            return res;
        }
        ll dp[MAXN];
        void dp_dfs(int node, int p)
        {
            if(node != 1 ) dp[node]=(ll)(s[node])+(ll)(v[node])*depth[node]+get_val((ll)(v[node]));
         
            line l;
            l.node=node;
            l.k=-depth[node];
            l.n=dp[node];
            add_line(&l, 1, 0, sz-1);
            for(auto i:T[node])
            {
                if(i.first!=p)
                {
                    dp_dfs(i.first,node);
                }
            }
            pop_line(l);
        }
        int main()
        {
            ios_base::sync_with_stdio(false);
            cin.tie(0);cout.tie(0);
            int n;
            cin>>n;
            for(int i=1;i<n;i++)
            {
                int u1,v1;
                ll w;
                cin>>u1>>v1>>w;
                T[u1].emplace_back(v1,w);
                T[v1].emplace_back(u1,w);
            }
            s[1]=0, v[1]=0;
            for(int i=2;i<=n;i++)
                cin>>s[i]>>v[i];
            depth[1]=0;
            depth_dfs(1,1);
            make_lichao(n);
            dp[1]=0;
            dp_dfs(1,1);
            for(int i=2;i<=n;i++)
                cout<<dp[i]<<" ";
            cout<<endl;
            return 0;
        }

Compilation message (stderr)

harbingers.cpp: In function 'void make_lichao(int)':
harbingers.cpp:36:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             while(xx.size()<sz) xx.push_back(0);
      |                   ~~~~~~~~~^~~

• Subtask 1: 90 / 100