結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2021-04-08 19:02:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#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;}