oj.uz

Submission #1063335

# Submission time Handle Problem Language Result Execution time Memory
1063335 2024-08-17T16:59:13 Z avighna Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 12684 KB 
#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::vector<bool> which(n - 1);
    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]) {
          which[up[node].second] = true;
          node = up[node].first;
        }
      }
    }
    ll ans = 0;
    for (ll i = 0; i < n - 1; ++i) {
      if (which[i]) {
        ans += weights[i];
      }
    }
    std::cout << ans << '\n';
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 12684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 7196 KB Output is correct
2 Execution timed out 1035 ms 11704 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1047 ms 12684 KB Time limit exceeded
3 Halted 0 ms 0 KB -