#1187846 (C++17) No.3720 Balanced Reduction

• 問題: No.3720 Balanced Reduction
• ユーザー: 👑 Nachia
• 提出日時: 2026-09-19 00:51:14
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 2,812 bytes
• コンパイル時間: 807 ms
• コンパイル使用メモリ: 114,656 KB
• 実行使用メモリ: 36,552 KB
• 最終ジャッジ日時: 2026-09-19 00:51:19
• 合計ジャッジ時間: 4,215 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 4
other	AC * 14 WA * 2

ソースコード

// TODO

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }


void testcase(){
  ll N, K; cin >> N >> K;
  V<ll> A(N); REP(i,N) cin >> A[i];
  V<set<ll>> adj(N);
  REP(i,N){
    ll u,v; cin >> u >> v; u--; v--;
    adj[u].insert(v);
    adj[v].insert(u);
  }
  auto remedge = [&](ll u, ll v){
    adj[u].erase(v);
    adj[v].erase(u);
  };
  ll offset = 0;
  {
    V<ll> que;
    REP(i,N) if(adj[i].size() == 1) que.push_back(i);
    while(que.size()){
      ll v = que.back(); que.pop_back();
      ll w = adj[v].begin().operator*();
      if(0 < A[v] && A[v] < K){ cout << "-1\n"; return; }
      if(0 < A[v]) offset += (A[v] + (K * 2 - 1)) / (K * 2);
      A[w] -= A[v];
      A[v] = 0;
      if(A[w] < 0){ cout << "-1\n"; return; }
      remedge(v, w);
      if(adj[w].size() == 1) que.push_back(w);
    }
  }
  V<ll> seq, B;
  REP(i,N) if(adj[i].size()){
    ll v = i;
    while(adj[v].size()){
      ll w = adj[v].begin().operator*();
      seq.push_back(w);
      B.push_back(A[w]);
      remedge(v, w);
      v = w;
    }
  }
  
  // cout << offset << endl;
  // for(auto a : B) cout << a << " "; cout << endl;

  ll M = B.size();
  if(M % 2 == 1){
    ll ans = offset;
    V<ll> Q(M);
    REP(i,M) Q[M-1] += (B[i] * (i % 2 ? -1 : 1));
    if(Q[M-1] % 2 != 0){ cout << "-1\n"; return; } Q[M-1] /= 2;
    REP(i,M-1) Q[i] = B[i] - Q[(i+M-1)%M];
    if(Q[M-1] != B[M-1] - Q[M-2]){ cout << "-1\n"; return; }
    for(ll q : Q) if(q < 0 || (0 < q && q < K)){ cout << "-1\n"; return; }
    for(ll q : Q){
      if(0 < q) ans += (q + (K * 2 - 1)) / (K * 2);
    }
    cout << ans << "\n";
    return;
  }

  REP(i,M-1) B[i+1] -= B[i];
  if(B[M-1] != 0){ cout << "-1\n"; return; }

  V<ll> G, H;
  REP(i,M) (i%2 == 0? G : H).push_back(B[i]);
  sort(G.begin(), G.end());
  sort(H.begin(), H.end());
  ll ans = INF;
  REP(h,2){
    ll g = G[0];
    auto nG = G;
    auto nH = H;
    for(auto& a : nG) a -= g;
    for(auto& a : nH) a += g;
    ll tmp = 0;
    for(ll q : nG) if(q < 0 || (0 < q && q < K)) tmp = INF;
    for(ll q : nH) if(q < 0 || (0 < q && q < K)) tmp = INF;
    for(ll q : nG) if(0 < q) tmp += (q + (K * 2 - 1)) / (K * 2);
    for(ll q : nH) if(0 < q) tmp += (q + (K * 2 - 1)) / (K * 2);
    chmin(ans, offset + tmp);
    swap(G, H);
  }
  if(ans > INF / 2) ans = -1;
  cout << ans << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}