oj.uz

Submission #320018

# Submission time Handle Problem Language Result Execution time Memory
320018 2020-11-07T09:29:43 Z tushar_2658 Harbingers (CEOI09_harbingers) C++14
100 / 100
 169 ms 23764 KB 
#include "bits/stdc++.h"
using namespace std;

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

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

struct line {
  ll M, C;
  line(ll _M, ll _C){
    M = _M;
    C = _C;
  }
  line(){}
};

line CHT[maxn];
int ptr = 1;

ll f(ll x, int idx){
  return CHT[idx].M * x + CHT[idx].C;
}

ll query(ll x){
  int lo = 1, hi = ptr - 1;
  while(lo <= hi){
    int mid = (lo + hi) >> 1;
    if(f(x, mid) <= f(x, mid + 1))lo = mid + 1;
    else hi = mid - 1;
  }
  return f(x, lo);
}

double intersect(line x, line y){
  return (double)(y.C - x.C) * 1.0 / (double)(x.M - y.M) * 1.0;
}

int insert(line x){
  int lo = 2, hi = ptr;
  while(lo <= hi){
    int mid = (lo + hi) >> 1;
    if(intersect(CHT[mid - 1], CHT[mid]) >= intersect(CHT[mid - 1], x)){
      hi = mid - 1;
    }else {
      lo = mid + 1;
    }
  }
  return lo;
}

void dfs(int x, int p, ll dis){
  d[x] = dis;
  line prv;
  ll prv_sz = ptr;
  int id;
  if(p){
    ll res = query(m[x]);
    dp[x] = c[x] + (d[x] * m[x]) - res;
    line cur = line(d[x], -dp[x]);
    id = insert(cur);
    prv = CHT[id];
    ptr = id;
    CHT[id] = cur;
  }
  for(auto i : edges[x]){
    if(i.first != p){
      dfs(i.first, x, dis + i.second);
    }
  }
  if(p){
    CHT[id] = prv;
    ptr = prv_sz;
  }
}

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;
  CHT[1] = {0, 0};
  dfs(1, 0, 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:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
harbingers.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%d %d %lld", &x, &y, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%lld %lld", &c[i], &m[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 5 ms 3948 KB Output is correct
3 Correct 57 ms 12516 KB Output is correct
4 Correct 87 ms 16356 KB Output is correct
5 Correct 123 ms 20196 KB Output is correct
6 Correct 152 ms 23764 KB Output is correct
7 Correct 76 ms 13668 KB Output is correct
8 Correct 169 ms 19184 KB Output is correct
9 Correct 157 ms 20988 KB Output is correct
10 Correct 128 ms 19420 KB Output is correct