제출 #726432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726432		YENGOYAN	Graph (BOI20_graph)	C++17	17 / 100	3 ms	340 KiB

Graph

/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e9;

vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };

void solve() {
  int n, m; cin >> n >> m;
  vector<vector<pair<int, int>>> gp(n);
  for(int i = 0; i < m; ++i){
    int u, v, w; cin >> u >> v >> w; w *= 10;
    gp[--u].push_back({--v, w});
    gp[v].push_back({u, w});
  }
  vector<int> ans(n, inf), val(n), comp;
  vector<bool> vis;
  int sm = 0;
  function<void(int)> dfs = [&](int u){
    vis[u] = 1;
    if(sm != inf) {
      sm += abs(val[u]);
    }
    comp.push_back(u);
    for(pair<int, int> &v : gp[u]) {
      if(!vis[v.first]) {
        val[v.first] = v.second - val[u];
        dfs(v.first); 
      }
      else if(val[u] + val[v.first] != v.second) {
         sm = inf;
      }
    }
  };
  vector<double> res(n);
  vector<int> st;
  for(int a = -50; a <=50; ++a){
    vis = vector<bool> (n);
    val = vector<int> (n);
    for(int i = 0; i < n; ++i) {
      if(vis[i]) {
        continue;
      }
      if(a == -50) {
        st.push_back(i);
      }
      sm = 0;
      val[i] = a;
      comp.clear();
      dfs(i);
      if(sm < ans[i]) {
        ans[i] = sm;
        for(int &u : comp) {
          res[u] = val[u];
        }
      }
    }
  }
  for(int &u : st){
    if(ans[u] == inf){ 
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
  for(int i = 0; i < n; ++i) {
    cout << double(res[i] / 10) << " ";
  }
  cout << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 // int t; cin >> t; while(t--)
    solve();
}

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