結果

問題 No.3220 Forest Creation
コンテスト
ユーザー woshinailong
提出日時 2025-08-01 22:25:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,428 bytes
コンパイル時間 1,806 ms
コンパイル使用メモリ 206,872 KB
実行使用メモリ 10,788 KB
最終ジャッジ日時 2025-08-01 22:25:21
合計ジャッジ時間 5,263 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Fenwick，维护两个量：count 和 degree-sum
struct Fenwick {
    int n;
    vector<ll> cnt, sum;
    Fenwick(int _n): n(_n), cnt(n+1), sum(n+1) {}
    // add v to count[pos], add w to sum[pos]
    void update(int pos, ll v, ll w){
        for(int i=pos; i<=n; i+=i&-i){
            cnt[i] += v;
            sum[i] += w;
        }
    }
    // query [1..pos]
    pair<ll,ll> query(int pos){
        ll c=0, s=0;
        for(int i=pos; i>0; i-=i&-i){
            c += cnt[i];
            s += sum[i];
        }
        return {c,s};
    }
    // query [l..r]
    pair<ll,ll> range(int l, int r){
        if(l>r) return {0,0};
        auto R = query(r);
        auto L = query(l-1);
        return {R.first - L.first, R.second - L.second};
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> A(N+1);
    ll n = 0, M = 0;
    for(int d=0; d<=N; d++){
        cin >> A[d];
        n += A[d];
        M += (ll)d * A[d];
    }
    // 基本森林必要条件
    if((M&1) || M > 2*(n-1)){
        cout << "No\n";
        return 0;
    }

    // 收集所有度值块，并降序
    vector<pair<int,ll>> degs;
    for(int d=0; d<=N; d++){
        if(A[d]>0) degs.emplace_back(d, A[d]);
    }
    sort(degs.begin(), degs.end(),
         [&](auto &x, auto &y){ return x.first > y.first; });

    // Fenwick 初始化：在度值轴上标注所有剩余点
    Fenwick fw(N);
    for(int d=0; d<=N; d++){
        if(A[d]>0){
            fw.update(d, A[d], (ll)d*A[d]);
        }
    }
    ll totalSum = M;  // 当前 Fenwick 中所有度的总和

    // 前缀已选 K 个点，度和 sumL
    ll K = 0, sumL = 0;
    for(auto &blk : degs){
        int d = blk.first;
        ll cnt = blk.second;

        // 1) 并入前缀
        K    += cnt;
        sumL += (ll)d * cnt;
        // 2) 从 Fenwick 中“删掉”这 cnt 个点
        fw.update(d, -cnt, -(ll)d*cnt);
        totalSum -= (ll)d*cnt;

        // 3) 计算剩余中度 > K 的数量和度和
        auto [cntBig, sumBig] = fw.range(K+1, N);

        // 4) Erdős–Gallai RHS = K*(K-1) + cntBig*K + (totalSum - sumBig)
        ll rhs = K*(K-1) + cntBig*K + (totalSum - sumBig);
        if(sumL > rhs){
            cout << "No\n";
            return 0;
        }
    }

    // 全部通过
    cout << "Yes\n";
    return 0;
}
0