oj.uz

Submission #320006

# Submission time Handle Problem Language Result Execution time Memory
320006 2020-11-07T07:05:43 Z tushar_2658 Harbingers (CEOI09_harbingers) C++14
20 / 100
 26 ms 24172 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 26 ms 24172 KB Output is correct
3 Runtime error 1 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)