제출 #155038

#제출 시각아이디문제언어결과실행 시간메모리
155038junodeveloperNetwork (BOI15_net)C++14
100 / 100
710 ms116472 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() #define fi first #define se second using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int maxn=500000; int n,D[maxn+10][2]; vector<int> adj[maxn+10]; vector<pii> res; void solve(int p,int u) { vector<int> ones,twos; for(auto& it:adj[u]) { if(it==p) continue; solve(u,it); if(D[it][1]) twos.push_back(it); else if(D[it][0]) ones.push_back(it); } while(sz(twos)>=2) { res.push_back({D[twos.back()][1],D[twos[sz(twos)-2]][1]}); ones.push_back(twos.back()); ones.push_back(twos[sz(twos)-2]); twos.pop_back();twos.pop_back(); } if(!twos.empty()&&ones.empty()) { D[u][0]=D[twos[0]][0]; D[u][1]=D[twos[0]][1]; return; } if(!twos.empty()) { res.push_back({D[twos.back()][1],D[ones.back()][0]}); ones.pop_back();ones.push_back(twos.back()); twos.pop_back(); } while(sz(ones)>=3) { res.push_back({D[ones.back()][0],D[ones[sz(ones)-2]][0]}); ones.pop_back();ones.pop_back(); } if(u==p) { if(sz(ones)==1) res.push_back({u,D[ones.back()][0]}); else if(sz(ones)==2) res.push_back({D[ones.back()][0],D[ones[sz(ones)-2]][0]}); } else if(sz(adj[u])==1) D[u][0]=u; else { if(sz(ones)>=1) D[u][0]=D[ones[0]][0]; if(sz(ones)>=2) D[u][1]=D[ones[1]][0]; } } int main() { scanf("%d",&n); int i; for(i=0;i+1<n;i++) { int u,v; scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } int rt=-1; for(i=1;i<=n;i++) if(sz(adj[i])!=1) rt=i; solve(rt,rt); printf("%d\n",sz(res)); for(auto& it:res) printf("%d %d\n",it.fi,it.se); return 0; }

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

net.cpp: In function 'int main()':
net.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
net.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...