#1187229 (C++23) No.3720 Balanced Reduction

• 問題: No.3720 Balanced Reduction
• ユーザー: ぽえ
• 提出日時: 2026-09-17 21:03:33
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 139 ms / 2,000 ms
• コード長: 4,063 bytes
• コンパイル時間: 2,764 ms
• コンパイル使用メモリ: 361,700 KB
• 実行使用メモリ: 30,288 KB
• 最終ジャッジ日時: 2026-09-18 20:51:36
• 合計ジャッジ時間: 5,136 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 4
other	AC * 16

ソースコード

#include <bits/stdc++.h>
using namespace std;

#line 2 "misc/interval-union.hpp"

// Union of [a_1, b_1), [a_2, b_2), ...
template <typename T>
vector<pair<T, T>> interval_union(const vector<pair<T, T>> &v) {
  vector<pair<T, T>> buf{v}, res;
  sort(begin(buf), end(buf));
  for (auto &p : buf) {
    res.push_back(p);
    while ((int)res.size() >= 2) {
      int n = res.size();
      if (res[n - 2].second < res[n - 1].first) break;
      pair<T, T> q;
      q.first = res[n - 2].first;
      q.second = max<T>(res[n - 2].second, res[n - 1].second);
      res.pop_back();
      res.pop_back();
      res.push_back(q);
    }
  }
  return res;
}

/**
 * @brief 区間の集合の直和
 * https://nyaannyaan.github.io/library/misc/interval-union.hpp.html
 */

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; ll k; cin >> n >> k;
    ll m = 2*k, ans = 0;
    vector<ll> a(n);
    for (auto& i : a) cin >> i;
    vector<vector<int>> g(n);
    vector<int> d(n);
    for (int i=0; i<n; i++) {
        int u, v; cin >> u >> v; u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        d[u]++; d[v]++;
    }
    
    queue<int> q;
    for (int i=0; i<n; i++) if (d[i] == 1) q.push(i);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        if (a[v]<0 || (0<a[v] && a[v]<k)) {
            cout << -1 << '\n';
            return 0;
        }
        ans += (a[v]+m-1)/m;
        d[v] = 0;
        for (auto& u : g[v]) if (d[u]) {
            a[u] -= a[v];
            if (--d[u] == 1) q.push(u);
        }
    }
    int rt = 0;
    while (!d[rt]) rt++;
    vector<ll> c;
    int v = rt, p = -1;
    do {
        c.push_back(a[v]);
        int u = -1;
        for (auto& w : g[v]) if (d[w] && w!=p) u = w;
        p = v; v = u;
    } while (v != rt);
    int z = c.size();
    vector<ll> b(z);
    for (int i=1; i<z; i++) b[i] = c[i]-b[i-1];
    if (z%2) {
        ll t = c[0]-b.back();
        if (t%2) {
            cout << -1 << '\n';
            return 0;
        }
        t /= 2;
        for (int i=0; i<z; i++) {
            ll x = b[i]+(i%2 ? -t : t);
            if (x<0 || (x>0 && x<k)) {
                cout << -1 << '\n';
                return 0;
            }
            ans += (x+m-1)/m;
        }
        cout << ans << '\n';
        return 0;
    }
    if (b.back() != c[0]) {
        cout << -1 << '\n';
        return 0;
    }
    ll l = 0, r = 1'000'000'000;
    vector<pair<ll,ll>> gar;
    for (int i=0; i<z; i++) {
        if (i%2) {
            r = min(r,b[i]);
            gar.emplace_back(b[i]-k+1,b[i]);
        } else {
            l = max(l,-b[i]);
            gar.emplace_back(1-b[i],k-b[i]);
        }
    }
    vector<pair<ll,ll>> ranges;
    ll cur = l;
    for (auto& [i, j] : interval_union(gar)) {
        if (cur < min(i,r+1)) ranges.emplace_back(cur,min(i,r+1));
        cur = max(cur,j);
    }
    if (cur <= r) ranges.emplace_back(cur,r+1);
    vector<pair<ll,ll>> residues;
    for (auto& [i, j] : ranges) {
        if (m <= j-i) {
            residues.emplace_back(0,m);
            break;
        }
        ll x = i%m, y = (j-1)%m;
        if (x <= y) residues.emplace_back(x,y+1);
        else {
            residues.emplace_back(x,m);
            residues.emplace_back(0,y+1);
        }
    }
    residues = interval_union(residues);
    vector<pair<ll,ll>> ev;
    ll f = 0;
    for (int i=0; i<z; i++) {
        f += b[i]/m+(b[i]%m>0);
        ll x = ((i%2 ? b[i] : 1-b[i])%m+m)%m;
        if (x) ev.emplace_back(x,i%2 ? -1 : 1);
    }
    ev.emplace_back(m,0);
    sort(ev.begin(),ev.end());
    ll best = numeric_limits<ll>::max(), prev = 0;
	int ptr = 0;
	for (auto& [i, j] : ev) {
	    while (ptr < (int)residues.size() &&
	           residues[ptr].second <= prev) {
	        ptr++;
	    }
	    if (prev < i &&
	        ptr < (int)residues.size() &&
	        residues[ptr].first < i) {
	        best = min(best, f);
	    }
	    f += j;
	    prev = i;
	}
    
    cout << (best==numeric_limits<ll>::max() ? -1 : ans+best) << '\n';
}