結果

問題 No.1752 Up-Down Tree
ユーザー harurunharurun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 long
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;
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 DEBUG
cerr<<point+1<<" "<<res/num<<" "<<res%num<<endl;
#endif
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;
}
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 DEBUG
for(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0