結果
問題 | No.1928 Make a Binary Tree |
ユーザー |
![]() |
提出日時 | 2021-12-09 10:51:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,043 bytes |
コンパイル時間 | 1,171 ms |
コンパイル使用メモリ | 82,620 KB |
実行使用メモリ | 526,404 KB |
最終ジャッジ日時 | 2024-11-06 04:22:56 |
合計ジャッジ時間 | 8,448 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 MLE * 1 -- * 23 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <vector>#include <iostream>#include <utility>#include <algorithm>#include <queue>using namespace std;vector<int> Graph[200010];bool checked[200010];priority_queue<int> vec[200010];int dfs(int i,int parent){checked[i]=true;for(int to:Graph[i]){if(!checked[to]){int p=dfs(to,i);vec[i].push(p);}}int res=1;if(vec[i].size()<=2){while(!vec[i].empty()){res+=vec[i].top();vec[i].pop();}}else{for(int j=0;j<2;j++){res+=vec[i].top();vec[i].pop();}if(parent!=-1){while(!vec[i].empty()){vec[parent].push(vec[i].top());vec[i].pop();}}}return res;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int N;cin>>N;for(int i=0; i<N-1; i++){int x,y;cin>>x>>y;Graph[x-1].emplace_back(y-1);Graph[y-1].emplace_back(x-1);}int ans=dfs(0,-1);cout<<ans<<"\n";}