제출 #1340343

#제출 시각아이디문제언어결과실행 시간메모리
1340343repmannGraph (BOI20_graph)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector <pair <int, int>> VG[200002];
int V[200002], DIST[200002];
bitset <200002> B;
int O[200002];
void DFS(int node, int root)
{
  V[node] = root;
  for(pair <int, int> p : VG[node])
  {
    if(V[p.second] != root) {DIST[p.second] = DIST[node] + p.first; DFS(p.second, root);}
    else if((DIST[node] + p.first) != DIST[p.second]) {cout << "NO\n"; exit(0);}
  }
  return;
}
void DFSV(int node, int root, vector <int> &U)
{
  V[node] = root;
  U.push_back(node);
  for(pair <int, int> p : VG[node]) if(V[p.second] != root) DFSV(p.second, root, U);
  return;
}
void DFSO(int node)
{
  B[node] = 1;
  for(pair <int, int> p : VG[node])
  {
    if(B[p.second]) continue;
    O[p.second ^ 1] = -(O[p.second] = O[node] + (p.first << 1));
    DFSO(p.second);
  }
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << setprecision(10) << fixed;
  cin >> N >> M;
  int u, v, w;
  for(int i = 1; i <= M; i++)
  {
    cin >> u >> v >> w;
    VG[u << 1 | 1].push_back({-w, v << 1});
    VG[v << 1].push_back({+w, u << 1 | 1});
    VG[v << 1 | 1].push_back({-w, u << 1});
    VG[u << 1].push_back({+w, v << 1 | 1});
  }
  for(int i = 2; i <= (N << 1 | 1); i++) if(!V[i]) DFS(i, i);
  for(int i = 1; i <= N; i++)
  {
    if(B[i << 1] || B[i << 1 | 1]) continue;
    if(V[i << 1] == V[i << 1 | 1])
    {
      DFS(i << 1, i << 1);
      O[i << 1 | 1] = DIST[i << 1 | 1];
      DFSO(i << 1 | 1);
    }
    else
    {
      vector <int> U;
      DFSV(V[i << 1], -V[i << 1], U);
      int l = -2 * (int)U.size(), r = +2 * (int)U.size(), s, ret;
      int sum0 = 0, sum1 = 0;
      while(l <= r)
      {
        s = (l + r) / 2;
        for(int x : U) sum0 += abs(s + DIST[x]), sum1 += abs(s + 1 + DIST[x]);
        if(sum0 > sum1) l = s + 1;
        else {r = s - 1; ret = s;}
      }
      O[V[i << 1]] = -(O[V[i << 1] ^ 1] = ret);
      DFSO(i << 1);
    }
  }
  cout << "YES\n";
  for(int i = 1; i <= N; i++) cout << (O[i << 1 | 1] / 2.0) << " \n"[i == N];

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...