Submission #479579

#	Time	Username	Problem	Language	Result	Execution time	Memory
479579		Mackerel_Pike	Harbingers (CEOI09_harbingers)	C++14	0 / 100	178 ms	30180 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define PB push_back
#define MP make_pair

const int maxn = 1e5 + 5;
const int logn = 20;

int n;
int v[maxn], s[maxn];
int par[maxn], top[maxn], pre[maxn][logn], dep[maxn];
long long f[maxn], k[maxn], b[maxn];
long double p[maxn];
vector<pair<int, int> > g[maxn];

inline void dfs(int u, int par){
  if(~par){
    top[u] = top[par];
    int x = top[u];
    for(int i = logn - 1; i >= 0; --i)
      if(~pre[x][i] && p[pre[x][i]] > dep[u])
	x = pre[x][i];
    x = pre[x][0];
    //printf("u = %d x = %d\n", u, x);
    f[u] = k[x] * v[u] + b[x] + s[u] + 1ll * v[u] * dep[u];
  }
  else{
    top[u] = -1;
    f[u] = 0;
  }
  // f[u] = f[v] + v[u] * (dep[u] - dep[v]) + s[u]
  b[u] = f[u];
  k[u] = -dep[u];
  for(; ~top[u] &&
	k[top[u]] * p[u] + b[top[u]] >= k[u] * p[u] + b[u]; top[u] = pre[top[u]][0]);
  if(!~top[u])
    p[u] = -1e9;
  else
    p[u] = 1.0l * (b[top[u]] - b[u]) / (k[u] - k[top[u]]);
  pre[u][0] = top[u], top[u] = u;
  for(int i = 1; i < logn; ++i)
    pre[u][i] = (~pre[u][i - 1] ? pre[pre[u][i - 1]][i - 1] : -1);
  for(int i = 0; i < g[u].size(); ++i){
    int v = g[u][i].fst, w = g[u][i].snd;
    if(v == par)
      continue;
    dep[v] = dep[u] + w;
    dfs(v, u);
  }
  return;
}

int main(){
  //freopen("D.in", "r", stdin);
  
  scanf("%d", &n);
  for(int i = 1; i < n; ++i){
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    --u, --v;
    g[u].PB(MP(v, w));
    g[v].PB(MP(u, w));
  }

  for(int i = 1; i < n; ++i)
    scanf("%d%d", s + i, v + i);
  dfs(0, -1);
  for(int i = 1; i < n; ++i)
    printf("%lld ", f[i]); puts("");
  return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < g[u].size(); ++i){
      |                  ~~^~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:71:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |   for(int i = 1; i < n; ++i)
      |   ^~~
harbingers.cpp:72:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |     printf("%lld ", f[i]); puts("");
      |                            ^~~~
harbingers.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
harbingers.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     int u, v, w; scanf("%d%d%d", &u, &v, &w);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d%d", s + i, v + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100