結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー GOTKAKO
提出日時 2025-12-12 02:12:45
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 286 ms / 2,000 ms
コード長 1,751 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,939 ms
コンパイル使用メモリ 205,136 KB
実行使用メモリ 60,148 KB
最終ジャッジ日時 2025-12-12 02:12:53
合計ジャッジ時間 7,938 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int N; cin >> N;
    vector<vector<int>> edge(N),siz(N),Graph(N);
    vector<pair<int,int>> UV(N-1,{-1,-1});
    for(int i=0; i<N; i++){
        int k; cin >> k;
        siz.at(k).push_back(i);
        while(k--){
            int v; cin >> v,v--;
            edge.at(i).push_back(v);
            if(UV.at(v).first == -1) UV.at(v).first = i;
            else UV.at(v).second = i;
        }
    }
    for(int i=0; i<N; i++) for(auto &pos : edge.at(i)){
        auto [u,v] = UV.at(pos);
        if(i == u) pos = v;
        else pos = u;
    }
    vector<int> answer(N);
    vector<int> ok(N),ok2,look(N,N);
    for(int s=N-1; s>0; s--){
        for(auto pos : siz.at(s)){
            ok.at(pos) = 1;
            for(auto to : edge.at(pos)){
                if(ok.at(to)) Graph.at(pos).push_back(to),Graph.at(to).push_back(pos);
            }
            ok2.push_back(pos);
        }

        int ans = 0;
        auto dfs = [&](auto dfs,int pos,int back) -> bool {
            look.at(pos) = s;
            bool ret = true;
            if(back == -1) ret = false;
            int use = edge.at(pos).size()-Graph.at(pos).size();
            for(auto to : Graph.at(pos)){
                if(to == back) continue;
                if(dfs(dfs,to,pos)) use++;
            }
            if(use >= s) ans++;
            else if(use+ret >= s) ans++,ret = false;
            return ret;
        };
        for(auto root : ok2){
            if(look.at(root) == s) continue;
            dfs(dfs,root,-1);
        }
        answer.at(s) = ans;
    }
    answer.erase(answer.begin());
    for(auto a : answer) cout << a << " "; cout << "\n";
}
0