Submission #1063326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063326		avighna	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	1060 ms	14776 KiB

roadsideadverts

#include <bits/stdc++.h>

typedef long long ll;

struct Edge {
  ll v, w, i;
};

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

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

  ll q;
  std::cin >> q;
  while (q--) {
    std::vector<ll> nodes(5);
    for (auto &i : nodes) {
      std::cin >> i;
    }
    std::set<ll> st;
    for (ll i = 0; i < 5; ++i) {
      std::vector<ll> depth(n);
      std::vector<std::pair<ll, ll>> up(n);
      std::function<void(ll, ll)> dfs;
      dfs = [&](ll node, ll par) {
        for (auto &[i, w, idx] : adj[node]) {
          if (i == par) {
            continue;
          }
          depth[i] = depth[node] + 1;
          up[i] = {node, idx};
          dfs(i, node);
        }
      };
      dfs(nodes[i], -1);
      for (ll j = i + 1; j < 5; ++j) {
        ll node = nodes[j];
        while (node != nodes[i]) {
          st.insert(up[node].second);
          node = up[node].first;
        }
      }
    }
    ll ans = 0;
    for (auto &i : st) {
      ans += weights[i];
    }
    std::cout << ans << '\n';
  }
}

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