結果
問題 | No.1752 Up-Down Tree |
ユーザー | harurun |
提出日時 | 2021-11-19 23:23:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,300 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 107,216 KB |
実行使用メモリ | 359,532 KB |
最終ジャッジ日時 | 2024-06-10 10:53:33 |
合計ジャッジ時間 | 5,574 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 99 ms
20,992 KB |
testcase_01 | AC | 97 ms
15,360 KB |
testcase_02 | AC | 86 ms
15,736 KB |
testcase_03 | AC | 84 ms
15,780 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <unordered_map> #include <deque> #include <utility> #include <queue> using namespace std; int main(){ int N; cin>>N; vector<vector<int>> G(N); for(int i=0;i<N-1;i++){ int A,B; cin>>A>>B; G[A-1].push_back(B-1); G[B-1].push_back(A-1); } deque<pair<int,int>> dq; dq.push_back(make_pair(0,0)); vector<int> depth(N,-1); while(!dq.empty()){ pair<int,int> q=dq.back();dq.pop_back(); depth[q.first]=q.second; for(int to:G[q.first]){ if(depth[to]==-1){ dq.push_back(make_pair(to,q.second+1)); } } } // cerr<<"depth"<<endl; // for(int i=0;i<N;i++){ // cerr<<depth[i]<<" "; // }cerr<<endl; vector<int> parent(N); parent[0]=-1; vector<vector<int>> children(N); priority_queue<pair<int,int>> pq; for(int i=0;i<N;i++){ for(int to:G[i]){ if(depth[i]<depth[to]){ //cerr<<"c "<<i<<" "<<to<<endl; children[i].push_back(to); }else{ //cerr<<"p "<<i<<" "<<to<<endl; parent[i]=to; } } if(children[i].empty()){ pq.push(make_pair(depth[i],i)); } } // for(int i=0;i<N;i++){ // cerr<<parent[i]<<" "; // }cerr<<endl; vector<int> num(N,1); while(!pq.empty()){ pair<int,int> q=pq.top(); pq.pop(); int point=q.second; int par=parent[point]; if(par==-1){ break; } if(num[par]!=1){ continue; } if(children[par].size()<=2){ //cerr<<"par:"<<par<<endl; for(int i:children[par]){ num[par]+=num[i]; //cerr<<i<<" "<<num[i]<<endl; }//cerr<<endl; }else{ vector<pair<int,int>> cnt; for(int i:children[par]){ cnt.push_back(make_pair(num[i],i)); } sort(cnt.rbegin(),cnt.rend()); num[par]+=cnt[0].first+cnt[1].first; if(parent[par]!=-1){ for(int i=2;i<cnt.size();i++){ parent[cnt[i].second]=parent[par]; children[parent[par]].push_back(cnt[i].second); } } } pq.push(make_pair(depth[par],par)); } // for(int i=0;i<N;i++){ // for(auto j:children[i]){ // cerr<<i<<" "<<j<<endl; // } // } // for(int i=0;i<N;i++){ // cerr<<num[i]<<" "; // }cerr<<endl; cout<<num[0]<<endl; return 0; }