Submission #443937

#	Time	Username	Problem	Language	Result	Execution time	Memory
443937		MKutayBozkurt	Harbingers (CEOI09_harbingers)	C++17	0 / 100	102 ms	14144 KiB

harbingers

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct node {
  int p, s; // prep, speed
};

int32_t main() {
  //freopen("harbingers.in", "r", stdin);
  //freopen("harbingers.out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  vector<vector<pair<int, int>>> g(n);
  vector<node> nodes(n + 1);
  vector<pair<int, int>> pr(n); // parent
  for (int i = 0; i < n - 1; i++) {
    int a, b, c; cin >> a >> b >> c, a--, b--;
    if (a > b) swap(a, b);
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
    pr[b] = {a, c};
  }
  for (int i = 1; i <= n - 1; i++) {
    int p, s; cin >> p >> s;
    nodes[i] = node{p, s};
  }

  function<int(int, int)> f = [&](int node, int har) {
    if (node == 0) return 0ll;
    int st = nodes[node].p + pr[node].second * nodes[node].s;
    int nd = nodes[har].s * pr[node].second;
    if (node == har) {
      return st + f(pr[node].first, node);
    }
    if (st < nd) {
      return st + f(pr[node].first, node);
    } else {
      return nd + f(pr[node].first, har);
    }
  };

  for (int i = 1; i <= n - 1; i++) {
    cout << f(i, i) << " ";
  }
  cout << '\n';
}

• Subtask 1: 0 / 100