Submission #1182171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182171		avighna	Designated Cities (JOI19_designated_cities)	C++20	0 / 100	121 ms	32928 KiB

designated_cities

#include <bits/stdc++.h>

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

  int n;
  std::cin >> n;
  std::vector<std::vector<std::pair<int, std::pair<long long, long long>>>> adj(
      n + 1);
  long long tot = 0;
  for (int i = 0, a, b, c, d; i < n - 1; ++i) {
    std::cin >> a >> b >> c >> d;
    adj[a].push_back({b, {c, d}});
    adj[b].push_back({a, {d, c}});
    tot += c + d;
  }

  std::vector<std::vector<std::pair<int, long long>>> adj2(n + 1);
  long long up = 0;
  auto dfs = [&](auto &&self, int u, int p) -> void {
    for (auto &[i, pr] : adj[u]) {
      if (i == p) {
        continue;
      }
      auto [c, d] = pr;
      up += d;
      adj2[u].push_back({i, c});
      adj2[i].push_back({u, c});
      self(self, i, u);
    }
  };
  dfs(dfs, 1, 0);

  auto diameter =
      [&](int n, std::vector<std::vector<std::pair<int, long long>>> &adj) {
        std::pair<long long, long long> pr = {0, 1};
        auto dfs = [&](auto &&self, int u, int p, int d) -> void {
          for (auto &[i, wt] : adj[u]) {
            if (i == p) {
              continue;
            }
            if (d + wt > pr.first) {
              pr.first = d + wt;
              pr.second = i;
            }
            self(self, i, u, d + wt);
          }
        };
        dfs(dfs, 1, 0, 0);
        int u = pr.second;
        pr = {0, u};
        dfs(dfs, u, 0, 0);
        return pr.first;
      };

  long long ans = up + diameter(n, adj2);

  int q;
  std::cin >> q;
  while (q--) {
    int x;
    std::cout << tot - ans << '\n';
  }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44