結果

問題 No.763 Noelちゃんと木遊び
ユーザー ytftytft
提出日時 2021-04-08 19:02:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 3,354 bytes
コンパイル時間 2,694 ms
コンパイル使用メモリ 191,656 KB
実行使用メモリ 37,112 KB
最終ジャッジ日時 2024-06-23 21:58:42
合計ジャッジ時間 6,367 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 143 ms
37,112 KB
testcase_01 AC 51 ms
13,620 KB
testcase_02 AC 123 ms
27,224 KB
testcase_03 AC 82 ms
19,544 KB
testcase_04 AC 58 ms
15,148 KB
testcase_05 AC 77 ms
18,936 KB
testcase_06 AC 153 ms
32,212 KB
testcase_07 AC 150 ms
31,688 KB
testcase_08 AC 86 ms
20,284 KB
testcase_09 AC 56 ms
14,596 KB
testcase_10 AC 23 ms
7,808 KB
testcase_11 AC 153 ms
32,736 KB
testcase_12 AC 131 ms
29,380 KB
testcase_13 AC 165 ms
29,096 KB
testcase_14 AC 123 ms
26,352 KB
testcase_15 AC 80 ms
19,436 KB
testcase_16 AC 15 ms
6,940 KB
testcase_17 AC 83 ms
19,500 KB
testcase_18 AC 155 ms
32,448 KB
testcase_19 AC 132 ms
29,900 KB
testcase_20 AC 138 ms
29,848 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