Submission #225131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225131	2020-04-19T09:48:19 Z	MKopchev	Harbingers (CEOI09_harbingers)	C++14	100 / 100	171 ms	16760 KB

harbingers

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n;

vector< pair<int/*to*/,int/*size*/> > adj[nmax];
int depth[nmax];

long long dp[nmax];

int parent[nmax];

int start[nmax],speed[nmax];

void dfs(int node,int par)
{
    for(auto k:adj[node])
        if(k.first!=par)
        {
            depth[k.first]=depth[node]+k.second;
            parent[k.first]=node;

            dfs(k.first,node);
        }
}

pair<int/*a*/,long long/*b*/> active[nmax];//ax+b

double cross(pair<int/*a*/,long long/*b*/> u,pair<int/*a*/,long long/*b*/> v)
{
    return 1.0*(u.second-v.second)/(v.first-u.first);
}
long long ask(int pos,int x)
{
    return 1LL*active[pos].first*x+active[pos].second;
}
int pointer=0;

long long ask_query(int x)
{
    if(pointer==0)return 0;
    long long ret=0;

    ret=min(ret,ask(1,x));
    ret=min(ret,ask(pointer,x));

    int ok=0,not_ok=pointer;
    while(not_ok-ok>1)
    {
        int av=(ok+not_ok)/2;

        ret=min(ret,ask(av,x));
        ret=min(ret,ask(av+1,x));

        if(cross(active[av],active[av+1])<=x)ok=av;
        else not_ok=av;
    }
    return ret;
}
void solve(int node,int par)
{
    pair<int/*a*/,long long/*b*/> mem_active;
    int mem_pointer;

    if(node!=1)
    {
        dp[node]=ask_query(speed[node]);

        dp[node]+=start[node]+1LL*depth[node]*speed[node];

        pair<int/*a*/,long long/*b*/> current={-depth[node],dp[node]};

        int ok=pointer,not_ok=0;

        while(ok-not_ok>1)
        {
            int av=(ok+not_ok)/2;

            if(cross(active[av],active[av+1])>=cross(active[av],current))ok=av;
            else not_ok=av;
        }

        mem_active=active[ok+1];
        mem_pointer=pointer;

        pointer=ok+1;
        active[pointer]=current;
    }

    for(auto k:adj[node])
        if(k.first!=par)
        {
            solve(k.first,node);
        }

    if(node!=1)
    {
        active[pointer]=mem_active;
        pointer=mem_pointer;
    }
}
int main()
{
    scanf("%i",&n);

    int u,v,d;
    for(int i=1;i<n;i++)
    {
        scanf("%i%i%i",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }

    for(int i=2;i<=n;i++)scanf("%i%i",&start[i],&speed[i]);

    dfs(1,0);

    solve(1,0);

    for(int i=2;i<=n;i++)
    {
        printf("%lld",dp[i]);
        if(i==n)printf("\n");
        else printf(" ");
    }
    return 0;
}

Compilation message

harbingers.cpp: In function 'int main()':
harbingers.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
harbingers.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&u,&v,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:114:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=2;i<=n;i++)scanf("%i%i",&start[i],&speed[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp: In function 'void solve(int, int)':
harbingers.cpp:99:16: warning: 'mem_pointer' may be used uninitialized in this function [-Wmaybe-uninitialized]
         pointer=mem_pointer;
         ~~~~~~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	2688 KB	Output is correct
2	Correct	8 ms	3072 KB	Output is correct
3	Correct	73 ms	8824 KB	Output is correct
4	Correct	117 ms	11772 KB	Output is correct
5	Correct	138 ms	14072 KB	Output is correct
6	Correct	146 ms	16760 KB	Output is correct
7	Correct	95 ms	9420 KB	Output is correct
8	Correct	171 ms	13556 KB	Output is correct
9	Correct	171 ms	15352 KB	Output is correct
10	Correct	168 ms	14420 KB	Output is correct