Submission #225064

#	Time	Username	Problem	Language	Result	Execution time	Memory
225064		MKopchev	Harbingers (CEOI09_harbingers)	C++14	20 / 100	1099 ms	15352 KiB

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);
        }
}

void solve(int node,int par)
{
    if(node!=1)
    {
        dp[node]=1LL*depth[node]*speed[node];

        int p=parent[node];
        while(p!=1)
        {
            dp[node]=min(dp[node],dp[p]+1LL*speed[node]*(depth[node]-depth[p]));
            p=parent[p];
        }

        dp[node]+=start[node];
    }
    for(auto k:adj[node])
        if(k.first!=par)
        {
            solve(k.first,node);
        }
}
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 (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
harbingers.cpp:55: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:60: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]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100