結果

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

ソースコード

diff # 

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

// Constants
const int MAXN = 5e5 + 5;
const ll MAX_K = 1e15; // Max possible K (|w_i| * N)

// Graph representation
vector<vector<pair<int, int>>> adj(MAXN); // adj[u]: {neighbor, edge_index}
vector<ll> vertex_weights(MAXN); // w[i]: weight of vertex i
vector<ll> edge_diffs(MAXN); // d[e]: |u_e - v_e| for edge e
vector<int> degrees(MAXN); // Current degree of vertex
int N;

// Check if we can assign edge differences d_e <= max_diff
bool can_assign(ll max_diff, vector<ll>& assigned_diffs) {
    vector<ll> remaining_weights = vertex_weights; // Copy weights
    vector<int> remaining_deg = degrees; // Copy degrees
    queue<int> leaves;
    
    // Initialize leaves (vertices with degree 1)
    for (int i = 1; i <= N; ++i) {
        if (remaining_deg[i] == 1) leaves.push(i);
    }
    
    // Process vertices starting from leaves
    while (!leaves.empty()) {
        int u = leaves.front();
        leaves.pop();
        
        if (remaining_deg[u] == 0) continue; // Already processed
        
        // Find the one active neighbor
        for (auto [v, e_idx] : adj[u]) {
            if (remaining_deg[v] >= 0) {
                // Assign d_e = remaining weight of u
                ll needed = remaining_weights[u];
                if (needed < 0 || needed > max_diff) return false;
                assigned_diffs[e_idx] = needed;
                remaining_weights[u] -= needed;
                remaining_weights[v] -= needed;
                
                // Update degrees
                remaining_deg[u]--;
                remaining_deg[v]--;
                
                // If v becomes a leaf, add to queue
                if (remaining_deg[v] == 1 && v != u) leaves.push(v);
                break;
            }
        }
    }
    
    // Verify all weights are satisfied
    for (int i = 1; i <= N; ++i) {
        if (remaining_weights[i] != 0) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Read input
    cin >> N;
    if (N < 2 || N > 5e5) {
        cout << -1 << '\n'; // Invalid N
        return 0;
    }
    
    ll weight_sum = 0;
    for (int i = 1; i <= N; ++i) {
        cin >> vertex_weights[i];
        if (abs(vertex_weights[i]) > 1e9) {
            cout << -1 << '\n'; // Invalid w_i
            return 0;
        }
        weight_sum += vertex_weights[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'; // Invalid vertex
            return 0;
        }
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
        degrees[a]++;
        degrees[b]++;
    }
    
    // Check if sum of weights is even
    if (weight_sum % 2 != 0) {
        cout << -1 << '\n';
        return 0;
    }
    
    // Handle special case: N = 2
    if (N == 2) {
        if (vertex_weights[1] == vertex_weights[2] && vertex_weights[1] >= 0) {
            cout << vertex_weights[1] << '\n';
            // Optionally: cout << vertex_weights[1] << " " << 0 << '\n';
        } else {
            cout << -1 << '\n';
        }
        return 0;
    }
    
    // Binary search for minimum max_diff
    ll low = 0, high = MAX_K, min_max_diff = -1;
    vector<ll> final_diffs(N - 1, 0);
    
    while (low <= high) {
        ll mid = low + (high - low) / 2;
        vector<ll> temp_diffs(N - 1, 0);
        if (can_assign(mid, temp_diffs)) {
            min_max_diff = mid;
            final_diffs = temp_diffs;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    // Output result
    if (min_max_diff == -1) {
        cout << -1 << '\n';
    } else {
        cout << min_max_diff << '\n';
        // Optionally output u_e, v_e for each edge (u_e = d_e + 1, v_e = 1)
        /*
        for (int i = 0; i < N - 1; ++i) {
            if (final_diffs[i] == 0) {
                cout << 1 << " " << 1 << '\n'; // Minimum valid u_e, v_e
            } else {
                cout << final_diffs[i] + 1 << " " << 1 << '\n';
            }
        }
        */
    }
    
    return 0;
}
0