結果

問題 No.1752 Up-Down Tree
ユーザー harurunharurun
提出日時 2021-11-20 17:04:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,345 bytes
コンパイル時間 1,711 ms
コンパイル使用メモリ 118,748 KB
実行使用メモリ 53,068 KB
最終ジャッジ日時 2023-09-02 12:31:08
合計ジャッジ時間 7,600 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 286 ms
52,536 KB
testcase_01 AC 275 ms
53,068 KB
testcase_02 AC 110 ms
28,124 KB
testcase_03 AC 111 ms
28,848 KB
testcase_04 AC 225 ms
39,332 KB
testcase_05 AC 244 ms
44,668 KB
testcase_06 AC 186 ms
34,908 KB
testcase_07 AC 190 ms
35,120 KB
testcase_08 AC 139 ms
23,232 KB
testcase_09 AC 191 ms
28,500 KB
testcase_10 AC 8 ms
11,596 KB
testcase_11 AC 8 ms
11,560 KB
testcase_12 AC 8 ms
11,452 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 7 ms
11,596 KB
testcase_21 AC 8 ms
11,156 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

class ContinuousPriorityQueue{
  private:
    std::vector<std::priority_queue<pair<int,int>>> _vec;
    atcoder::segtree<std::pair<pair<int,int>,int>,_max,_e> _seg;
    // val,index
  public:
    ContinuousPriorityQueue(int maxsize=200000){
      _seg=atcoder::segtree<std::pair<pair<int,int>,int>,_max,_e>(maxsize);
      _vec.reserve(maxsize);
    }
    pair<int,int> top(int l,int r){
      assert(0<=l && l<_vec.size() && 0<=r && r<=_vec.size());
      return _seg.prod(l,r).first;
    }
    pair<int,int> pop(int l,int r){
      assert(0<=l && l<_vec.size() && 0<r && r<=_vec.size());
      std::pair<pair<int,int>,int> max_p=_seg.prod(l,r);
      if(max_p==_e()){
        return 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 max_p.first;
    }
    void add(int index,pair<int,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(pair<int,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<pair<int,int>>());
      return;
    }
    int size(){
      return _vec.size();
    }
    bool empty(int index){
      return _vec[index].empty();
    }
    bool range_empty(int l,int r){
      return _seg.prod(l,r)==_e();
    }
    void _print(){
      for(int i=0;i<_vec.size();i++){
        priority_queue<pair<int,int>> pq=_vec[i];
        while(!pq.empty()){
          cerr<<"("<<pq.top().first<<","<<pq.top().second<<")";
          pq.pop();
        }cerr<<endl;
      }
    }
};

vector<vector<int>> G;

ContinuousPriorityQueue CPQ;
vector<int> depth;
vector<int> parent;
vector<vector<int>> children;
vector<bool> searched;
unordered_set<int> deled;

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

vector<int> table;
vector<vector<int>> new_children;
vector<int> new_parent;

int dfs2(int point){
  vector<pair<int,int>> pq;
  int pre=CPQ.size();
  for(int to:children[point]){
    int tmp=dfs2(to);
    pq.push_back(make_pair(tmp,to));
  }
  int res=1;
  //cerr<<"point:"<<point+1<<" "<<CPQ.size()<<endl;
  //table[CPQ.size()]=point;
  CPQ.push_back();
  for(pair<int,int> i:pq){
    CPQ.add_back(i);
  }
  if(!CPQ.range_empty(pre,CPQ.size())){ 
    //cerr<<"pre:"<<pre<<endl;
    //cerr<<"size:"<<CPQ.size()<<endl;
    pair<int,int> t1=CPQ.pop(pre,CPQ.size());
    res+=t1.first;
    //assert(0<=t1.second && t1.second<table.size());
    //assert(0<=table[t1.second] && table[t1.second]<new_parent.size());
    new_parent[t1.second]=point;
    new_children[point].push_back(t1.second);
    //cerr<<"t1:"<<t1.first<<" "<<t1.second<<endl;
    if(!CPQ.range_empty(pre,CPQ.size())){
      pair<int,int> t2=CPQ.pop(pre,CPQ.size());
      res+=t2.first;
      //assert(0<=t2.second && t2.second<table.size());
      //assert(0<=table[t2.second] && table[t2.second]<new_parent.size());
      new_parent[t2.second]=point;
      new_children[point].push_back(t2.second);
      //cerr<<"t2:"<<t2.first<<" "<<t2.second<<endl;
    }
  }else{
    // pq is empty <-> CPQ[pre,size) is empty
  }
  //cerr<<"let serach"<<endl;
  if(!searched[point] && CPQ.range_empty(pre,CPQ.size())){
    int cnt=1;
    int p=parent[point];
    while(p!=-1 && children[p].size()==1){
      cnt++;
      searched[p]=true;
      p=parent[p];
    }
    if(cnt%2==0){
      res--;
      deled.insert(point);
    }
  }
  //cerr<<"res:"<<res<<endl;
  // CPQ._print();
  return res;
}

bool dfs3(int point){
  //cerr<<point<<endl;
  if(deled.find(point)!=deled.end()){
    return true;
  }
  for(int to:new_children[point]){
    if(dfs3(to)){
      return true;
    }
  }
  return false;
}

int main(){
  int N;
  cin>>N;
  G.resize(N);
  depth.resize(N,-1);
  parent.resize(N,-1);
  children.resize(N);
  searched.resize(N,false);
  table.resize(N,-1);
  new_parent.resize(N);
  new_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);
  //cerr<<"dfs2 end"<<endl;
  // for(int i=0;i<N;i++){
  //   cerr<<"i:"<<i+1<<endl;
  //   for(int j:new_children[i]){
  //     cerr<<j+1<<" ";
  //   }cerr<<endl;
  // }
  if(deled.size()>=1 && dfs3(0)){
    //cerr<<"ans++"<<endl;
    ans++;
  }
  cout<<ans<<endl;
  //CPQ._print();
  // for(int i=0;i<N;i++){
  //   cerr<<table[i]+1<<" ";
  // }cerr<<endl;
  
  // for(int i:deled){
  //   cerr<<i+1<<" ";
  // }cerr<<endl;
  return 0;
}
0