Submission #1063480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063480		avighna	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	152 ms	27392 KiB

roadsideadverts

#include <bits/stdc++.h>

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n;
  std::cin >> n;
  std::vector<std::vector<std::pair<ll, ll>>> adj(n);
  for (ll i = 0, u, v, w; i < n - 1; ++i) {
    std::cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }

  std::vector<std::vector<ll>> lift(n, std::vector<ll>(16));
  std::vector<std::vector<ll>> lift_sum(n, std::vector<ll>(16));
  std::vector<ll> depth(n);
  std::function<void(ll, ll)> dfs;
  dfs = [&](ll node, ll par) {
    for (auto &[i, w] : adj[node]) {
      if (i == par) {
        continue;
      }
      lift[i][0] = node;
      lift_sum[i][0] = w;
      depth[i] = depth[node] + 1;
      dfs(i, node);
    }
  };
  dfs(0, -1);

  for (ll bt = 1; bt < 16; ++bt) {
    for (ll i = 0; i < n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
      lift_sum[i][bt] = lift_sum[i][bt - 1] + lift_sum[lift[i][bt - 1]][bt - 1];
    }
  }

  auto lca = [&](ll u, ll v) {
    if (depth[u] > depth[v]) {
      std::swap(u, v);
    }
    ll k = depth[v] - depth[u];
    for (ll bt = 0; bt < 16; ++bt) {
      if (k & (1 << bt)) {
        v = lift[v][bt];
      }
    }
    if (u == v) {
      return u;
    }
    for (ll bt = 15; bt >= 0; --bt) {
      if (lift[u][bt] != lift[v][bt]) {
        u = lift[u][bt];
        v = lift[v][bt];
      }
    }
    return lift[u][0];
  };

  auto lca_mult = [&](const std::vector<ll> &nodes) {
    ll ans = nodes[0];
    for (ll i = 1; i < nodes.size(); ++i) {
      ans = lca(ans, nodes[i]);
    }
    return ans;
  };

  auto sum = [&](ll from, ll to) {
    ll k = depth[from] - depth[to];
    ll ans = 0;
    for (ll bt = 0; bt < 16; ++bt) {
      if (k & (1 << bt)) {
        ans += lift_sum[from][bt];
        from = lift[from][bt];
      }
    }
    return ans;
  };

  ll q;
  std::cin >> q;
  while (q--) {
    std::vector<ll> arr = {0, 0, 0, 0, 0};
    std::cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] >> arr[4];
    ll ans = 0;
    ll LCA = lca_mult(arr);
    for (ll mask = 1; mask < 32; ++mask) {
      std::vector<ll> nodes;
      for (ll i = 0; i < 5; ++i) {
        if (mask & (1 << i)) {
          nodes.push_back(arr[i]);
        }
      }
      ll cur = sum(lca_mult(nodes), LCA);
      if (__builtin_popcount(mask) % 2 == 1) {
        ans += cur;
      } else {
        ans -= cur;
      }
    }
    std::cout << ans << '\n';
  }
}

Compilation message (stderr)

roadsideadverts.cpp: In lambda function:
roadsideadverts.cpp:66:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (ll i = 1; i < nodes.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30