Submission #1207960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207960		avighna	Graph (BOI20_graph)	C++20	100 / 100	92 ms	21440 KiB

Graph

#include <bits/stdc++.h>

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

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

  std::vector<bool> vis(n + 1);
  std::vector<int> nodes;
  auto dfs = [&](auto &&self, int u) {
    if (vis[u]) {
      return;
    }
    vis[u] = true;
    nodes.push_back(u);
    for (auto &[i, c] : g[u]) {
      self(self, i);
    }
  };
  std::vector<int> comps, comp_of(n + 1);
  std::vector<std::vector<int>> in_comp(n + 1);
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) {
      continue;
    }
    dfs(dfs, i);
    in_comp[i] = nodes;
    comps.push_back(i);
    for (auto &u : nodes) {
      comp_of[u] = i;
    }
    nodes.clear();
  }
  vis.assign(n + 1, false);

  std::vector<std::pair<int, double>> val(n + 1);
  const int inf = 1e7;
  double x;
  bool x_found = false;
  auto dfs1 = [&](auto &&self, int u, int m, double c) {
    if (vis[u]) {
      auto [a, b] = val[u];
      if (a != m or std::abs(b - c) > 1e-6) {
        if (x_found) {
          return std::abs(m * x + c - a * x - b) < 1e-6;
        } else {
          if (m == a) {
            return false;
          }
          x = (b - c) / (m - a);
          return x_found = true;
        }
      }
      return true;
    }
    vis[u] = true;
    val[u] = {m, c};
    // val[u] + val[i] = {0, e}
    // val[i] = {0, e} - {m, c}
    for (auto &[i, e] : g[u]) {
      if (!self(self, i, -m, e - c)) {
        return false;
      }
    }
    return true;
  };
  std::vector<double> ans(n + 1);
  for (auto &u : comps) {
    if (!dfs1(dfs1, u, 1, 0)) {
      std::cout << "NO\n";
      return 0;
    }
    double _x;
    if (x_found) {
      _x = x;
    } else {
      std::vector<double> vals;
      for (auto &u : in_comp[u]) {
        auto [a, b] = val[u];
        if (a < 0) {
          a = -a, b = -b;
        }
        vals.push_back(-b);
      }
      std::sort(vals.begin(), vals.end());
      _x = vals[vals.size() / 2];
    }
    x_found = false;
    for (auto &u : in_comp[u]) {
      auto [m, c] = val[u];
      ans[u] = m * _x + c;
    }
  }

  std::cout << "YES\n";
  for (int i = 1; i <= n; ++i) {
    std::cout << ans[i] << ' ';
  }
  std::cout << '\n';
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 42 / 42
• Subtask 5: 5 / 5