oj.uz

Submission #225064

# Submission time Handle Problem Language Result Execution time Memory
225064 2020-04-19T08:53:24 Z MKopchev Harbingers (CEOI09_harbingers) C++14
20 / 100
 1000 ms 15352 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 27 ms 3072 KB Output is correct
3 Execution timed out 1085 ms 8184 KB Time limit exceeded
4 Execution timed out 1091 ms 10360 KB Time limit exceeded
5 Execution timed out 1093 ms 13048 KB Time limit exceeded
6 Execution timed out 1096 ms 15352 KB Time limit exceeded
7 Execution timed out 1089 ms 9592 KB Time limit exceeded
8 Execution timed out 1090 ms 12656 KB Time limit exceeded
9 Execution timed out 1095 ms 13688 KB Time limit exceeded
10 Execution timed out 1099 ms 13044 KB Time limit exceeded