結果
問題 | No.1752 Up-Down Tree |
ユーザー |
![]() |
提出日時 | 2021-11-20 18:10:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,698 bytes |
コンパイル時間 | 3,768 ms |
コンパイル使用メモリ | 124,072 KB |
最終ジャッジ日時 | 2025-01-25 22:11:40 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 WA * 5 |
ソースコード
#include <vector>#include <queue>#include <utility>#include <algorithm>#include <assert.h>#include <atcoder/segtree>#include <iostream>#include <unordered_set>using namespace std;#define int long longstd::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,indexpublic: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;const int num=100000;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=num;//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!=0 && children[p].size()==1){//cerr<<p+1<<" "<<children[p].size()<<endl;cnt++;searched[p]=true;p=parent[p];}if(cnt%2==0){if(res%num>0){res--;res+=num;}else{res-=num;res++;}//deled.insert(point);}}//cerr<<"res:"<<res<<endl;// CPQ._print();#ifdef DEBUGcerr<<point+1<<" "<<res/num<<" "<<res%num<<endl;#endifreturn 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;}signed 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;#ifdef DEBUGfor(int i=0;i<N;i++){cerr<<"i:"<<i+1<<endl;for(int j:new_children[i]){cerr<<j+1<<" ";}cerr<<endl;}#endif// if(deled.size()>=1 && dfs3(0)){// //cerr<<"ans++"<<endl;// ans+=num;// }if(ans%num!=0){ans+=num;}//cerr<<ans<<endl;cout<<ans/num<<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;}