結果

問題 No.1752 Up-Down Tree
ユーザー harurunharurun
提出日時 2021-11-19 23:23:21
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,300 bytes
コンパイル時間 1,475 ms
コンパイル使用メモリ 107,972 KB
実行使用メモリ 455,120 KB
最終ジャッジ日時 2025-01-01 22:21:27
合計ジャッジ時間 15,823 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 105 ms
22,056 KB
testcase_01 AC 129 ms
326,452 KB
testcase_02 AC 84 ms
22,468 KB
testcase_03 AC 87 ms
351,444 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 AC 66 ms
10,240 KB
testcase_09 WA -
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 1 ms
6,816 KB
testcase_21 AC 2 ms
449,364 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0