結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー seekworser
提出日時 2025-12-02 01:33:34
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,745 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,157 ms
コンパイル使用メモリ 288,608 KB
実行使用メモリ 39,924 KB
最終ジャッジ日時 2025-12-11 23:31:53
合計ジャッジ時間 12,956 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//line 1 "answer.cpp"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i=0; i<(n); i++)
#define all(a) a.begin(), a.end()
template<typename T> bool chmin(T &a, T b) {if (a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T &a, T b) {if (a < b){a = b; return true;} return false;}
template<typename Container> ll sz(const Container &a) {return a.size();}
const ll INFL = (1LL << 61);
struct Fastio {Fastio() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);}}; Fastio fastio;

int main() {
    ll n; cin >> n;
    vector<ll> deg(n, 0);
    vector edges(n-1, vector<ll>());
    rep(i, n) {
        cin >> deg[i];
        rep(_, deg[i]) {
            ll eid; cin >> eid; --eid;
            edges[eid].emplace_back(i);
        }
    }
    vector g(n, vector<ll>());
    rep(i, n-1) {
        ll u = edges[i][0];
        ll v = edges[i][1];
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<ll> ans(n-1, 0);
    for (ll k=1; k<=n-1; k++) {
        if (k > 20) break;
        auto dfs = [&] (auto self, ll u, ll par) -> pair<ll,ll> {
            ll dpn = 0;
            ll total = 0;
            for (auto v : g[u]) {
                if (v == par) continue;
                auto [dpi, tn] = self(self, v, u);
                total += tn;
                dpn += dpi;
            }
            if ((deg[u] - 1 - total) >= k) return {dpn+1, 0};
            if ((deg[u] - total) >= k) return {dpn+1, 1};
            return {dpn, 0};
        };
        auto [dp, _] = dfs(dfs, 0, -1);
        ans[k-1] = dp;
    }
    rep(i, sz(ans)) cout << ans[i] << " \n"[i == sz(ans) - 1];
}
0