結果

問題 No.3113 The farthest point
ユーザー Евгений Ивлев
提出日時 2025-04-18 23:30:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,517 bytes
コンパイル時間 2,416 ms
コンパイル使用メモリ 205,684 KB
実行使用メモリ 31,584 KB
最終ジャッジ日時 2025-04-18 23:31:03
合計ジャッジ時間 12,006 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Constants
const int MAXN = 500005; // 5e5 + 5

// Graph representation
vector<pair<int, int>> adj[MAXN]; // {neighbor, edge_index}
vector<ll> w(MAXN); // Vertex weights
vector<ll> d(MAXN); // Edge weight differences d_e
vector<int> deg(MAXN); // Degree of each vertex
int N;

// Check if we can assign d_e <= K
bool can_assign(ll K) {
    vector<ll> rem_w = w; // Remaining weight at each vertex
    vector<int> deg_rem = deg; // Remaining degree
    queue<int> q;
    
    // Initialize leaves
    for (int i = 1; i <= N; ++i) {
        if (deg_rem[i] == 1) q.push(i);
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (deg_rem[u] == 0) continue; // Already processed
        
        // Find the active neighbor
        for (auto [v, e_idx] : adj[u]) {
            if (deg_rem[v] >= 0) {
                ll need = rem_w[u];
                if (need < 0 || need > K) return false; // Invalid assignment
                d[e_idx] = need;
                rem_w[u] -= need;
                rem_w[v] -= need;
                deg_rem[u]--;
                deg_rem[v]--;
                
                if (deg_rem[v] == 1 && v != 1) q.push(v); // Avoid root if degree becomes 1
                break;
            }
        }
    }
    
    // Verify all weights are satisfied
    for (int i = 1; i <= N; ++i) {
        if (rem_w[i] != 0) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Read input
    cin >> N;
    ll sum_w = 0, max_w = 0;
    for (int i = 1; i <= N; ++i) {
        cin >> w[i];
        sum_w += w[i];
        max_w = max(max_w, abs(w[i]));
    }
    
    // Read edges
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
        deg[a]++;
        deg[b]++;
    }
    
    // Check feasibility
    if (sum_w % 2 != 0) {
        cout << -1 << '\n';
        return 0;
    }
    
    // Optimize binary search range
    ll lo = 0, hi = max_w * 2; // Tighter upper bound: max_w per vertex, at most doubled
    ll ans = -1;
    
    while (lo <= hi) {
        ll mid = lo + (hi - lo) / 2;
        if (can_assign(mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    
    // Output result
    cout << (ans == -1 ? -1 : ans) << '\n';
    
    return 0;
}
0