제출 #905939

#제출 시각아이디문제언어결과실행 시간메모리
905939dsyzNetwork (BOI15_net)C++17
0 / 100
4 ms12632 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (500005) ll N, connectto1 = -1, cnt = 0; ll pre[MAXN]; vector<ll> v[MAXN]; bool leaf[MAXN]; void dfs(ll x,ll p){ pre[x] = cnt++; ll children = 0; ll leafchildren = 0; for(auto u : v[x]){ if(u != p){ dfs(u,x); leafchildren += leaf[u]; if(leafchildren >= 2) connectto1 = u; children++; } } if(children == 0){ leaf[x] = 1; } } int main() { ios_base::sync_with_stdio(false);cin.tie(0); cin>>N; for(ll i = 0;i < N - 1;i++){ ll a,b; cin>>a>>b; a--, b--; v[a].push_back(b); v[b].push_back(a); } dfs(0,-1); vector<pair<ll,ll> > ans; for(ll i = 0;i < N;i++){ if(leaf[i] && i != connectto1){ ans.push_back({pre[i],i}); } } sort(ans.begin(),ans.end()); if(ans.size() + 1 == 1){ //graph is a line cout<<1<<'\n'; cout<<1<<" "<<ans[0].second + 1<<'\n'; }else if(ans.size() + 1 == 2){ cout<<2<<'\n'; cout<<1<<" "<<ans[0].second + 1<<'\n'; cout<<ans[0].second + 1<<" "<<ans[1].second + 1<<'\n'; }else{ cout<<ans.size() - 1 + 1<<'\n'; cout<<1<<" "<<connectto1 + 1<<'\n'; for(ll i = 1;i < ans.size();i++){ cout<<ans[i - 1].second + 1<<" "<<ans[i].second + 1<<'\n'; } } }

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

net.cpp: In function 'int main()':
net.cpp:53:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(ll i = 1;i < ans.size();i++){
      |                ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...