結果

問題 No.3220 Forest Creation
ユーザー woshinailong
提出日時 2025-08-01 22:23:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,072 bytes
コンパイル時間 1,759 ms
コンパイル使用メモリ 195,368 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-01 22:23:41
合計ジャッジ時間 3,560 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    int N;
    cin >> N;
    vector<ll> A(N+1);
    for(int i = 0; i <= N; i++){
        cin >> A[i];
    }

    // 1) 统计顶点总数 V 和度数之和 S
    ll V = 0, S = 0;
    for(int i = 0; i <= N; i++){
        V += A[i];
        S += (ll)i * A[i];
    }

    // 特殊小规模：0 个或 1 个顶点时，只能是空图或 1 个孤立点，S 必须为 0
    if(V <= 1){
        cout << (S == 0 ? "Yes\n" : "No\n");
        return 0;
    }

    // 必要条件 1：S 必须是偶数，且 S <= 2*(V-1)
    if( (S & 1) || S > 2*(V-1) ){
        cout << "No\n";
        return 0;
    }

    // 必要条件 2：不存在度数 ≥ V 的顶点
    // 因为 A 的下标最大到 N，但可能 N >= V，也要排除
    for(int i = V; i <= N; i++){
        if(A[i] > 0){
            cout << "No\n";
            return 0;
        }
    }

    // 如果都通过，就一定能构造出森林
    cout << "Yes\n";
    return 0;
}
0