結果

問題 No.763 Noelちゃんと木遊び
ユーザー galaxy_papergalaxy_paper
提出日時 2021-04-08 19:02:50
言語 C++14
(gcc 10.2.0 + boost 1.73.0)
結果
AC  
実行時間 153 ms / 2,000 ms
コード長 3,354 Byte
コンパイル時間 2,207 ms
使用メモリ 36,752 KB
最終ジャッジ日時 2021-04-08 19:02:58
合計ジャッジ時間 7,528 ms
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 129 ms
36,752 KB
testcase_01 AC 47 ms
13,372 KB
testcase_02 AC 114 ms
26,960 KB
testcase_03 AC 77 ms
19,292 KB
testcase_04 AC 55 ms
14,828 KB
testcase_05 AC 75 ms
18,876 KB
testcase_06 AC 141 ms
31,896 KB
testcase_07 AC 136 ms
30,856 KB
testcase_08 AC 83 ms
20,128 KB
testcase_09 AC 59 ms
14,344 KB
testcase_10 AC 23 ms
7,604 KB
testcase_11 AC 153 ms
32,396 KB
testcase_12 AC 128 ms
29,324 KB
testcase_13 AC 125 ms
28,948 KB
testcase_14 AC 109 ms
26,008 KB
testcase_15 AC 75 ms
18,848 KB
testcase_16 AC 14 ms
6,000 KB
testcase_17 AC 76 ms
19,316 KB
testcase_18 AC 144 ms
32,052 KB
testcase_19 AC 130 ms
29,456 KB
testcase_20 AC 127 ms
29,448 KB
権限があれば一括ダウンロードができます

ソースコード

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