Submission #1345332

#TimeUsernameProblemLanguageResultExecution timeMemory
1345332lyra_g13Roadside Advertisements (NOI17_roadsideadverts)C++20
7 / 100
1094 ms5432 KiB
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n;
  cin >> n;

  vector<vector<pair<ll, ll>>> adj(n + 1);
  set<ll> tree;

  for (int i = 0; i < n - 1; i++) {
    ll u, v, w;
    cin >> u >> v >> w;

    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }

  ll q;
  cin >> q;
  ll ans = 0;

  vector<ll> vis(n + 1);
  auto dfs = [&](auto &&self, ll u) -> ll {
    if (vis[u])
      return 0;
    ll subt = tree.count(u);
    vis[u] = 1;
    for (auto [v, w] : adj[u]) {
      if (vis[v])
        continue;
      ll child = self(self, v);
      if (child > 0) {
        ans += w;
      }
      subt += child;
    }
    return subt;
  };
  while (q--) {
    tree.clear();
    vis.assign(n + 1, 0);
    ans = 0;

    for (int i = 0; i < 5; i++) {
      ll u;
      cin >> u;
      tree.insert(u);
    }

    dfs(dfs, 0);
    cout << ans << "\n";
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...