제출 #1365826

#제출 시각아이디문제언어결과실행 시간메모리
1365826edoGraph (BOI20_graph)C++20
100 / 100
63 ms12916 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0, u, v, w; i < m; ++i) {
    cin >> u >> v >> w, --u, --v;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }

  vector<int> s(n), vis(n);
  vector<double> b(n), ans(n);

  for (int r = 0; r < n; ++r) {
    if (vis[r])
      continue;
    queue<int> q;
    q.push(r);
    vis[r] = 1;
    s[r] = 1;
    b[r] = 0;
    bool hasT = 0;
    vector<int> comp;
    double T = 0;
    while (q.size()) {
      int u = q.front();
      q.pop();
      comp.push_back(u);
      for (auto [v, w] : g[u]) {
        if (!vis[v]) {
          vis[v] = 1;
          s[v] = -s[u];
          b[v] = w - b[u];
          q.push(v);
        } else {
          int A = s[u] + s[v];
          double C = w - b[u] - b[v];
          if (!A) {
            if (fabsl(C) > 1e-12) {
              cout << "NO\n";
              return 0;
            }
          } else {
            double curT = C / A;
            if (!hasT) {
              hasT = 1;
              T = curT;
            } else {
              if (fabsl(T - curT) > 1e-12) {
                cout << "NO\n";
                return 0;
              }
            }
          }
        }
      }
    }
    if (!hasT) {
      vector<double> need;
      need.reserve(comp.size());
      for (int u : comp) {
        need.push_back(s[u] == 1 ? -b[u] : b[u]);
      }
      nth_element(need.begin(), need.begin() + need.size() / 2, need.end());
      T = need[need.size() / 2];
    }

    for (int u : comp) {
      ans[u] = s[u] * T + b[u];
    }
  }

  cout << "YES\n";
  cout << fixed << setprecision(12);
  for (auto x : ans) {
    cout << x << " ";
  }
  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…