結果

問題 No.1928 Make a Binary Tree
ユーザー harurunharurun
提出日時 2021-12-01 02:00:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 997 bytes
コンパイル時間 1,320 ms
コンパイル使用メモリ 104,648 KB
最終ジャッジ日時 2025-01-26 02:37:10
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 39 RE * 1
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <utility>
#include <atcoder/segtree>
using namespace atcoder;
using namespace std;
vector<vector<int>> Graph;
vector<bool> checked;
pair<int,int> op(pair<int,int> a,pair<int,int> b){
return a>b?a:b;
}
pair<int,int> e(){
return make_pair(-1,-1);
}
segtree<pair<int,int>,op,e> seg;
int searched=0;
int dfs(int i){
int pre=searched;
searched++;
checked[i]=true;
for(int to:Graph[i]){
if(!checked[to]){
seg.set(to,make_pair(dfs(to),to));
}
}
int res=1;
for(int j=0;j<2;j++){
pair<int,int> tmp=seg.prod(pre,searched);
if(tmp.first==-1){
break;
}
res+=tmp.first;
seg.set(tmp.second,e());
}
return res;
}
int main(){
int N;
cin>>N;
Graph.resize(N);
checked.resize(N,false);
for(int i=0;i<N;i++){
int x,y;
cin>>x>>y;
Graph[x-1].push_back(y-1);
Graph[y-1].push_back(x-1);
}
seg=segtree<pair<int,int>,op,e>(N);
int ans=dfs(0);
cout<<ans<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0