結果

問題 No.763 Noelちゃんと木遊び
ユーザー ytft
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0