結果

問題 No.763 Noelちゃんと木遊び
ユーザー ytftytft
提出日時 2021-04-08 19:02:50
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 3,354 bytes
コンパイル時間 2,442 ms
コンパイル使用メモリ 187,112 KB
実行使用メモリ 36,748 KB
最終ジャッジ日時 2023-09-06 03:06:48
合計ジャッジ時間 7,202 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 140 ms
36,748 KB
testcase_01 AC 52 ms
13,360 KB
testcase_02 AC 125 ms
27,564 KB
testcase_03 AC 83 ms
19,408 KB
testcase_04 AC 59 ms
14,968 KB
testcase_05 AC 80 ms
18,812 KB
testcase_06 AC 161 ms
31,976 KB
testcase_07 AC 151 ms
30,972 KB
testcase_08 AC 88 ms
20,472 KB
testcase_09 AC 57 ms
14,336 KB
testcase_10 AC 21 ms
7,884 KB
testcase_11 AC 159 ms
32,780 KB
testcase_12 AC 137 ms
29,596 KB
testcase_13 AC 135 ms
29,212 KB
testcase_14 AC 119 ms
25,976 KB
testcase_15 AC 80 ms
18,948 KB
testcase_16 AC 14 ms
6,140 KB
testcase_17 AC 83 ms
19,516 KB
testcase_18 AC 156 ms
31,940 KB
testcase_19 AC 142 ms
29,640 KB
testcase_20 AC 141 ms
29,668 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