Submission #320006

#	Time	Username	Problem	Language	Result	Execution time	Memory
320006		tushar_2658	Harbingers (CEOI09_harbingers)	C++14	20 / 100	26 ms	24172 KiB

harbingers

#include "bits/stdc++.h"
using namespace std;

const int maxn = 2505;
using ll = long long;

vector<pair<int, ll>> edges[maxn];
ll m[maxn], c[maxn];
ll dp[maxn], d[maxn];

void dfs(int x, int p, vector<int> v, ll dis){
  d[x] = dis;
  if(x != 1){
    for(auto i : v){
      dp[x] = min(dp[x], dp[i] + (d[x] - d[i])*m[x] + c[x]);
    }
  }
  for(auto i : edges[x]){
    if(i.first != p){
      v.push_back(x);
      dfs(i.first, x, v, dis + i.second);
    }
  }
}

int main(int argc, char const *argv[])
{
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n - 1; ++i){
    int x, y;
    ll C;
    scanf("%d %d %lld", &x, &y, &C);
    edges[x].push_back({y, C});
    edges[y].push_back({x, C});
  }
  for(int i = 2; i <= n; ++i){
    scanf("%lld %lld", &c[i], &m[i]);
  }
  memset(dp, 63, sizeof dp);
  dp[1] = 0;
  dfs(1, 1, {}, 0);
  for(int i = 2; i <= n; ++i){
    printf("%lld ", dp[i]);
  }

  return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main(int, const char**)':
harbingers.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
harbingers.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d %d %lld", &x, &y, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%lld %lld", &c[i], &m[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100