제출 #1340329

#제출 시각아이디문제언어결과실행 시간메모리
1340329repmannGraph (BOI20_graph)C++20
0 / 100
2 ms344 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M;
vector <pair <int, int>> VG[200002];
int V[200002], DIST[200002], SIZE[200002];
ll SUM[200002];
bitset <200002> B;
int O[200002];
void DFS(int node, int root)
{
  V[node] = root;
  SUM[node] = 0;
  SIZE[node] = 1;
  for(pair <int, int> p : VG[node])
  {
    if(V[p.second] != root)
    {
      DIST[p.second] = DIST[node] + p.first; DFS(p.second, root);
      SUM[node] += SIZE[p.second] * p.first + SUM[p.second];
      SIZE[node] += SIZE[p.second];
    }
    else if((DIST[node] + p.first) != DIST[p.second]) {cout << "NO\n"; exit(0);}
  }
  return;
}
pair <ll, int> DFSMIN(int node, int root, ll sum = 0)
{
  V[node] = root;
  pair <ll, int> ret = {sum + SUM[node], node};
  for(pair <int, int> p : VG[node])
  {
    if(V[p.second] == root) continue;
    ret = min(DFSMIN(p.second, root, sum + (N - SIZE[p.second]) * p.first), ret);
  }
  return ret;
}
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);
      continue;
    }
    DFSO(DFSMIN(V[i << 1], -V[i << 1]).second);
  }
  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...