제출 #75933

#제출 시각아이디문제언어결과실행 시간메모리
75933VasiljkoNetwork (BOI15_net)C++14
0 / 100
54 ms49404 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9+7; const int N = 5e5+5; const int LOG = 19; int n,par[N][LOG],d[N]; vector<int>v[N],leaves; vector<pair<int,int> >ans; map<pair<int,int>,bool>exist; void dfs(int s,int p){ if(v[s].size()==1)leaves.push_back(s); par[s][0]=p; if(p!=-1)d[s]=d[p]+1; for(int i=1;i<LOG;i++)if(par[s][i-1]!=-1)par[s][i]=par[par[s][i-1]][i-1]; for(auto e:v[s])if(e!=p)dfs(e,s); } int LCA(int s,int t){ if(d[s]<d[t])swap(s,t); int dist=d[s]-d[t]; for(int i=LOG-1;i>=0;i--)if(dist&(1<<i))s=par[s][i]; if(s==t)return s; for(int i=LOG-1;i>=0;i--){ if(par[s][i]!=par[t][i]){ s=par[s][i]; t=par[t][i]; } } return par[s][0]; } int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); memset(par,-1,sizeof(par)); int x,y; cin>>n; for(int i=1;i<=n-1;i++){ cin>>x>>y; exist[{x,y}]=true; exist[{y,x}]=true; v[x].push_back(y); v[y].push_back(x); } dfs(1,-1); bool ok=false; for(int i=0;i<(int)leaves.size()/2;i++){ if(i<leaves.size()-i-1){ ans.push_back({leaves[i],leaves[(int)leaves.size()-i-1]}); if(LCA(leaves[i],leaves[(int)leaves.size()-i-1])<=1)ok=true; } } if((int)leaves.size()%2==1){ int node=leaves[(int)leaves.size()/2]; if(!exist[{1,node}])ans.push_back({1,leaves[(int)leaves.size()/2]}); else { int ind=(int)leaves.size()/2; if(ind)ans.push_back({leaves[ind-1],leaves[ind]}); else ans.push_back({leaves[ind],leaves[ind+1]}); } }else{ if(!ok){ if(leaves[0]!=1)ans.push_back({1,leaves[0]}); else ans.push_back({1,leaves[1]}); } } cout<<(int)ans.size()<<"\n"; for(auto e:ans)cout<<e.first<<" "<<e.second<<"\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

net.cpp: In function 'int main()':
net.cpp:58:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i<leaves.size()-i-1){
            ~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...