結果

問題 No.763 Noelちゃんと木遊び
ユーザー ytft
提出日時 2021-04-08 19:02:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 3,354 bytes
コンパイル時間 2,463 ms
コンパイル使用メモリ 183,732 KB
実行使用メモリ 36,824 KB
最終ジャッジ日時 2025-03-22 10:39:12
合計ジャッジ時間 6,000 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename verticesValueType,typename edgesValueType>
class Graph{
public:
    vector<vector<int>> edges;
    vector<int> parent;
    int numberOfVertices;
    vector<vector<int>> adjacencyMatrix;
    vector<vector<int>> connected;
    vector<vector<int>> children;
    vector<verticesValueType> verticesValue;
    vector<edgesValueType> edgesValue;
    Graph(vector<vector<int>> e,int N){
        edges=e;
        numberOfVertices=N;
    }
    vector<vector<int>> getConnected(){
        if(connected.size()>0)return connected;
        if(edges.size()>0){
            connected.resize(numberOfVertices);
            for(int i=connected.size()-1;i>=0;--i){
                connected[i]={};
            }
            for(int i=edges.size()-1;i>=0;i--){
                connected[edges[i][0]].push_back(edges[i][1]);
                connected[edges[i][1]].push_back(edges[i][0]);
            }
        }
        return connected;
    }
    vector<int> getParent(int root=0){
        if(parent.size()>0)return parent;
        parent.resize(numberOfVertices);
        vector<bool> isWritten(numberOfVertices);
        vector<vector<int>> c=getConnected();
        queue<vector<int>> q;
        q.push({-1,root});
        while(!q.empty()){
            if(isWritten[q.front()[1]]){
                goto end;
            }
            isWritten[q.front()[1]]=true;
            parent[q.front()[1]]=q.front()[0];
            for(int i:connected[q.front()[1]]){
                q.push({q.front()[1],i});
            }
            end:{}
            q.pop();
        }
        return parent;
    }
    vector<vector<int>> getChildren(int root=0){
        getParent(root);
        if(children.size()>0)return children;
        children.resize(numberOfVertices);
        for(int i=children.size()-1;i>=0;--i){
            children[i]={};
        }
        for(int i=0;i<numberOfVertices;i++){
            if(parent[i]>-1){
                children[parent[i]].push_back(i);
            }
        }
        return children;
    }
    vector<int> orderFromChildren(){
        getParent();
        getChildren();
        vector<int> ret(0);
        vector<int> count(numberOfVertices);
        queue<int> q;
        for(int i=0;i<numberOfVertices;i++){
            if(children[i].size()==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            ret.push_back(q.front());
            if(parent[q.front()]==-1){
                return ret;
            }
            ++count[parent[q.front()]];
            if(count[parent[q.front()]]==children[parent[q.front()]].size()){
                q.push(parent[q.front()]);
            }
            q.pop();
        }
        return ret;
    }
};

int main(){
    int N;
    cin>>N;
    vector<vector<int>> edges(0,vector<int>(2));
    int a,b;
    for(int i=0;i<N;i++){
        cin>>a>>b;
        edges.push_back({a-1,b-1});
    }
    Graph<int,int> g(edges,N);
    vector<int> o=g.orderFromChildren();
    vector<vector<int>> ans(N,vector<int>(2,0));
    vector<vector<int>> c=g.getChildren();
    for(int i:o){
        a=1;
        b=0;
        for(int j:c[i]){
            a+=ans[j][1];
            b+=max(ans[j][0],ans[j][1]);
        }
        ans[i][0]=a;
        ans[i][1]=b;
    }
    
    cout<<max(ans[0][0],ans[0][1])<<endl;
}
0