제출 #108713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108713		ckodser	Network (BOI15_net)	C++14	100 / 100	1369 ms	105848 KiB

net

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=5e5+500;
const ll inf=1e9+900;

vector<ll> ger[maxn];
set<pii> st;
vector<ll> barg;

pii dfs(ll a,ll p=-1){
    if(ger[a].size()==1){
	barg.pb(a);
	return mp(a,-1);
    }
    vector<pii> vec2;
    vector<ll> vec1;
    for(auto v:ger[a]){
	if(v!=p){
	    pii r=dfs(v,a);
	    if(r.S==-1)vec1.pb(r.F);
	    else       vec2.pb(r);
	}
    }
    if(vec2.size()==1){
	if(vec1.empty()){
	    return vec2.back();
	}else{
	    pii e=vec2.back();
	    st.erase(e);
	    ll v=vec1.back();
	    vec1.pop_back();
	    st.insert(mp(e.F,v));
	    pii las=mp(e.F,v);
	    vec1.pb(e.S);
	    for(ll i=0;i+1<vec1.size();i+=2){
		st.insert(mp(vec1[i],vec1[i+1]));
	    }
	    if(vec1.size()%2==1){
		return mp(vec1.back(),-1);
	    }
	    else{
		return las;
	    }
	}
    }else{
	pii las;
	for(auto e:vec2){
	    st.erase(e);
	}
	for(ll i=0;i<vec2.size();i++){
	    pii e=mp(vec2[i].S,vec2[(i+1)%vec2.size()].F);
	    las=e;
	    st.insert(e);
	}
	for(ll i=0;i+1<vec1.size();i+=2){
	    st.insert(mp(vec1[i],vec1[i+1]));
	    las=mp(vec1[i],vec1[i+1]);
	}
	if(vec1.size()%2==1){
	    return mp(vec1.back(),-1);
	}
	else{
	    return las;
	}
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    for(ll i=1;i<n;i++){
	ll v,u;
	cin>>v>>u;
	ger[u].pb(v);
	ger[v].pb(u);
    }
    ll rot;
    for(ll i=1;i<=n;i++){
	if(ger[i].size()>1)rot=i;
    }
    pii r=dfs(rot);
    if(r.S==-1 && r.F!=-1){
	ll v=r.F;
	for(auto u:barg){
	    if(v!=u){
		st.insert(mp(u,v));
		break;
	    }
	}
    }		
    cout<<st.size()<<endl;
    for(auto e:st){
	cout<<e.F<<' '<<e.S<<endl;
    }	
}

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

net.cpp: In function 'std::pair<long long int, long long int> dfs(long long int, long long int)':
net.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(ll i=0;i+1<vec1.size();i+=2){
                 ~~~^~~~~~~~~~~~
net.cpp:61:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vec2.size();i++){
             ~^~~~~~~~~~~~
net.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i+1<vec1.size();i+=2){
             ~~~^~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:92:18: warning: 'rot' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pii r=dfs(rot);
                  ^

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37