結果

問題 No.3113 The farthest point
ユーザー Евгений Ивлев
提出日時 2025-04-18 23:32:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,162 bytes
コンパイル時間 2,357 ms
コンパイル使用メモリ 205,556 KB
実行使用メモリ 31,588 KB
最終ジャッジ日時 2025-04-18 23:32:59
合計ジャッジ時間 5,196 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 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 or invalid
        
        // Find an active neighbor
        bool found = false;
        for (auto [v, e_idx] : adj[u]) {
            if (v < 1 || v > N || e_idx < 0 || e_idx >= N - 1) return false; // Bounds check
            if (deg_rem[v] >= 0) {
                ll need = rem_w[u];
                if (need < 0 || need > K) return false; // Invalid assignment
                if (e_idx >= d.size()) return false; // Ensure d[e_idx] is valid
                d[e_idx] = need;
                rem_w[u] -= need;
                rem_w[v] -= need;
                deg_rem[u]--;
                deg_rem[v]--;
                
                if (deg_rem[v] == 1 && deg_rem[v] > 0) q.push(v);
                found = true;
                break;
            }
        }
        if (!found && deg_rem[u] > 0) return false; // No valid neighbor
    }
    
    // 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;
    if (N < 2 || N > 500000) {
        cout << -1 << '\n';
        return 0;
    }
    
    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;
        if (a < 1 || a > N || b < 1 || b > N) {
            cout << -1 << '\n';
            return 0;
        }
        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;
    }
    
    // Handle special case: N = 2
    if (N == 2) {
        if (w[1] != w[2]) {
            cout << -1 << '\n';
        } else {
            cout << w[1] << '\n';
        }
        return 0;
    }
    
    // Binary search for minimum K
    ll lo = 0, hi = max_w; // Tighter bound
    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