結果

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

ソースコード

diff # 

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

// Constants
const int MAXN = 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) {
    fill(d.begin(), d.begin() + N - 1, 0);
    vector<ll> rem_w = w; // Remaining weight at each vertex
    vector<int> deg_rem = deg; // Remaining degree
    queue<int> q;
    
    // Find leaves (vertices with degree 1)
    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 degree is 0, skip (already processed)
        if (deg_rem[u] == 0) continue;
        
        // Leaf or pseudo-leaf: has one neighbor
        for (auto [v, e_idx] : adj[u]) {
            if (deg_rem[v] >= 0) { // Neighbor still active
                // Assign d_e = remaining weight of u
                ll need = rem_w[u];
                if (need < 0 || need > K) return false; // Cannot satisfy
                d[e_idx] = need;
                rem_w[u] -= need;
                rem_w[v] -= need;
                
                // Reduce degrees
                deg_rem[u]--;
                deg_rem[v]--;
                
                // If v becomes a leaf, add to queue
                if (deg_rem[v] == 1) q.push(v);
                break;
            }
        }
    }
    
    // Check if 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;
    for (int i = 1; i <= N; ++i) {
        cin >> w[i];
        sum_w += 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 if sum of weights is even
    if (sum_w % 2 != 0) {
        cout << -1 << '\n'; // Impossible
        return 0;
    }
    
    // Binary search for minimum K
    ll lo = 0, hi = 1e15, ans = -1; // Large enough for |w_i| <= 10^9
    while (lo <= hi) {
        ll mid = lo + (hi - lo) / 2;
        if (can_assign(mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    
    // Output the result
    if (ans == -1) {
        cout << -1 << '\n'; // No solution
    } else {
        // Run can_assign again to get the d_e values
        can_assign(ans);
        cout << ans << '\n';
        // Optionally, output u_e, v_e for each edge
        // For edge e, set u_e = d_e, v_e = 0 (or adjust if u_e, v_e >= 1 required)
        /*
        for (int i = 0; i < N - 1; ++i) {
            cout << d[i] << " " << 0 << '\n';
        }
        */
    }
    
    return 0;
}
0