結果

問題 No.1752 Up-Down Tree
ユーザー harurunharurun
提出日時 2021-11-20 13:03:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,247 bytes
コンパイル時間 1,262 ms
コンパイル使用メモリ 95,584 KB
実行使用メモリ 41,728 KB
最終ジャッジ日時 2023-09-02 00:13:47
合計ジャッジ時間 4,870 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 198 ms
41,728 KB
testcase_01 AC 198 ms
40,832 KB
testcase_02 AC 87 ms
17,864 KB
testcase_03 AC 86 ms
17,748 KB
testcase_04 AC 158 ms
29,884 KB
testcase_05 AC 170 ms
33,840 KB
testcase_06 AC 135 ms
24,992 KB
testcase_07 AC 138 ms
24,888 KB
testcase_08 AC 103 ms
16,272 KB
testcase_09 AC 139 ms
19,648 KB
testcase_10 AC 5 ms
8,632 KB
testcase_11 AC 6 ms
8,796 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 6 ms
8,736 KB
testcase_21 AC 5 ms
8,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <atcoder/segtree>
#include <iostream>
using namespace std;

std::pair<int,int> _max(std::pair<int,int> a,std::pair<int,int> b){
  return a > b ? a : b;
}

std::pair<int,int> _e(){
  return std::make_pair(-1,-1);
}

class ContinuousPriorityQueue{
  private:
    std::vector<std::priority_queue<int>> _vec;
    atcoder::segtree<std::pair<int,int>,_max,_e> _seg;
    // val,index
  public:
    ContinuousPriorityQueue(int maxsize=200000){
      _seg=atcoder::segtree<std::pair<int,int>,_max,_e>(maxsize);
      _vec.reserve(maxsize);
    }
    int top(int l,int r){
      assert(0<=l && l<_vec.size() && 0<=r && r<=_vec.size());
      return _seg.prod(l,r).first;
    }
    int pop(int l,int r){
      assert(0<=l && l<_vec.size() && 0<r && r<=_vec.size());
      std::pair<int,int> max_p=_seg.prod(l,r);
      if(max_p==_e()){
        return -1;
      }
      int res=max_p.first;
      _vec[max_p.second].pop();
      if(_vec[max_p.second].empty()){
        _seg.set(max_p.second,_e());
      }else{
        _seg.set(max_p.second,std::make_pair(_vec[max_p.second].top(),max_p.second));
      }
      return res;
    }
    void add(int index,int val){
      assert(0<=index && index<_vec.size());
      _vec[index].push(val);
      _seg.set(index,std::make_pair(_vec[index].top(),index));
      return;
    }
    void add_back(int val){
      assert(!_vec.empty());
      _vec.back().push(val);
      _seg.set(_vec.size()-1,std::make_pair(_vec.back().top(),_vec.size()-1));
      return;
    }
    void push_back(){
      _vec.push_back(std::priority_queue<int>());
      return;
    }
    int size(){
      return _vec.size();
    }
    bool empty(int index){
      return _vec[index].empty();
    }
    void _print(){
      for(int i=0;i<_vec.size();i++){
        priority_queue<int> pq=_vec[i];
        while(!pq.empty()){
          cout<<pq.top()<<" ";
          pq.pop();
        }cout<<endl;
      }
    }
};

vector<vector<int>> G;

ContinuousPriorityQueue CPQ;
vector<int> depth;
vector<int> parent;
vector<vector<int>> children;

void dfs(int point,int dep){
  depth[point]=dep;
  for(int to:G[point]){
    if(depth[to]==-1){
      dfs(to,dep+1);
      children[point].push_back(to);
    }else{
      parent[point]=to;
    }
  }
  return;
}

int dfs2(int point){
  vector<int> pq;
  int pre=CPQ.size();
  for(int to:children[point]){
    int tmp=dfs2(to);
    pq.push_back(tmp);
  }
  int res=1;
  //cerr<<"point:"<<point+1<<endl;
  if(!pq.empty()){
    CPQ.push_back();
    for(int i:pq){
      CPQ.add_back(i);
    }
    //cerr<<"pre:"<<pre<<endl;
    //cerr<<"size:"<<CPQ.size()<<endl;
    int t1=CPQ.pop(pre,CPQ.size());
    res+=max(0,t1);
    //cerr<<"t1:"<<t1<<endl;

    int t2=CPQ.pop(pre,CPQ.size());
    res+=max(0,t2);
    //cerr<<"t2:"<<t2<<endl;
  }
  //cerr<<"res:"<<res<<endl;
  // CPQ._print();
  return res;
}

int main(){
  int N;
  cin>>N;
  G.resize(N);
  depth.resize(N,-1);
  parent.resize(N,-1);
  children.resize(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);
  }
  dfs(0,0);
  int ans=dfs2(0);
  cout<<ans<<endl;
  //CPQ._print();
  return 0;
}
0