Submission #1024695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024695		NeroZein	Graph (BOI20_graph)	C++17	100 / 100	367 ms	36184 KiB

Graph

#include "bits/stdc++.h"
using namespace std;
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#pragma GCC target("avx2,fma")

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5;
const long long INF = 1e15;

bool vis[N];
bool vis2[N];
bool color[N];
stack<int> stk;
long long val[N];
vector<int> component;
vector<int> odd_cycle;
vector<pair<int, int>> g[N];

bool check_not_bipartite(int v, int c) {
  if (vis[v]) {
    if (color[v] != c && odd_cycle.empty()) {
      odd_cycle.push_back(v);
      while (true) {
        int x = stk.top();
        stk.pop();
        odd_cycle.push_back(x); 
        if (x == v) {
          break; 
        }
      }
      return true;
    }
    return false; 
  }
  vis[v] = true; 
  stk.push(v);
  color[v] = c; 
  component.push_back(v); 
  bool ret = false; 
  for (auto [u, w] : g[v]) {
    ret |= check_not_bipartite(u, c ^ 1); 
  }
  if (!stk.empty() && stk.top() == v) {
    stk.pop();    
  }
  return ret; 
}

long long assign(int v, long long c) {
  if (c > INF) {
    return INF;
  }
  if (vis2[v]) {
    if (val[v] != c) {
      return INF;
    }
    return 0;
  }
  vis2[v] = true;
  val[v] = c;
  long long ret = abs(c); 
  for (auto [u, w] : g[v]) {
    ret += assign(u, w - c);
    ret = min(ret, INF);
  }
  return ret; 
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  map<pair<int, int>, int> mp;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    w *= 2;
    if (u > v) swap(u, v);
    if (!mp.count({u, v})) {
      mp[{u, v}] = w;
      g[u].push_back({v, w});
      g[v].push_back({u, w});
    }
    if (mp[{u, v}] != w) {
      cout << "NO" << '\n';
      return 0; 
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) {
      continue; 
    }
    while (!stk.empty()) stk.pop();
    bool not_bipartite = check_not_bipartite(i, 0); 
    if (not_bipartite) {
      int sum = 0;
      for (int j = 1; j < (int) odd_cycle.size(); ++j) {
        int u = odd_cycle[j - 1], v = odd_cycle[j];
        if (u > v) swap(u, v);
        sum += mp[{u, v}] * (j % 2 ? 1 : -1);
      }
      int rt = odd_cycle[0];
      long long x = assign(rt, sum / 2);
      if (x == INF) {
        cout << "NO" << '\n';
        return 0; 
      }
      odd_cycle.clear();
    } else {
      int l = -2e5 - 9, r = 2e5 + 9;
      while (r - l > 3) {
        //int ml = l + (r - l) / 3;
        //int mr = r - (r - l) / 3;
        int mid = (l + r) / 2; 
        long long tmp = assign(i, mid);
        for (int v : component) {
          vis2[v] = false; 
        }
        long long tmp2 = assign(i, mid + 1);
        for (int v : component) {
          vis2[v] = false; 
        }
        if (tmp < tmp2) {
          r = mid + 1;
        } else {
          l = mid;
        }
      }
      long long mn = INF, uv = -1;
      for (int tval = l; tval <= r; tval++) {
        long long tmp = assign(i, tval);
        if (tmp < mn) {
          mn = tmp;
          uv = tval;
        }
        for (int v : component) {
          vis2[v] = false;
        }
      }
      if (uv == -1) {
        cout << "NO" << '\n';
        return 0; 
      }
      assign(i, uv); 
    }
    component.clear();
  }
  for (auto [e, w] : mp) {
    if (val[e.first] + val[e.second] != w) {
      cout << "NO" << '\n';
      return 0; 
    }
  }
  cout << "YES" << '\n';
  for (int i = 1; i <= n; ++i) {
    cout << (val[i] / 2.0) << ' ';
  }
  return 0;
}

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