제출 #394767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394767		mp007mp	Network (BOI15_net)	C++14	63 / 100	2075 ms	85032 KiB

net

        #include<bits/stdc++.h>
        #define S second 
        #define F first
        #define all(x) x.begin(),x.end()
        #define debug(x) cout<<#x<<" = "<<x<<"\n";
        using namespace std;
        typedef long long int ll;
        typedef long double ld;
        typedef pair<int,int> pii;
        ll mod = 1e9+7;
        int inf = 2e9;
        ll linf = 1000ll*1000*1000*1000*1000*1000;
        const int maxn = 500000+200;
        vector<pii> ans;
        vector<int> pth;
        set<int> adj[maxn];
        int sz[maxn],n;
        void gtsz(int v,int p){
        	sz[v] = (adj[v].size()>2)?1:0;
        	for(int u:adj[v]){
        		if(u == p)continue;
        		gtsz(u,v);
        		sz[v] += sz[u];
        	}
        	return;
        }
        int gtlf(int v,int p){
        	pth.push_back(v);
        	for(int u:adj[v]){
        		if(u == p)continue;
        		if(sz[u]>0){
        			pth.push_back(u);
        			return gtlf(u,v);
        		}
        	}
        	for(int u:adj[v]){
        		if(u == p)continue;
        		pth.push_back(u);
        		return gtlf(u,v);
        	}
        	return v;
        }
        void solve(){
          pth.clear();
        	int cnt=0,CNT=0;
        	int v;
        	vector<int> lvs;
        	for(int i=1;i<=n;i++){
        		if(adj[i].size()>3){
        			CNT = 1;
        		}
        		if(adj[i].size()>2){
        			cnt++;
        			v = i;
        		}
        		if(adj[i].size() == 1){
        			lvs.push_back(i);
        		}
        	}
        	if(lvs.size() == 0){
        		return;
        	}
        	if(CNT == 0 && cnt == 0){
        		cout<<lvs[0]<<" "<<lvs[1]<<"\n";
        		return;
        	}
        	if(CNT == 0 && cnt == 1){
        		cout<<lvs[0]<<" "<<lvs[1]<<"\n";
        		cout<<lvs[1]<<" "<<lvs[2]<<"\n";
        		return;
        	}
        	gtsz(v,v);
        	int ind1 = *adj[v].begin();
        	int ind2;
        	for(int u:adj[v]){
        		if(sz[u]>sz[ind1]){
        			ind1 = u;
        		}
        	}
        	for(int u:adj[v]){
        		if(ind1 != u){
        			ind2 = u;
        			break;
        		}
        	}
        	cout<<gtlf(ind1,v)<<" "<<gtlf(ind2,v)<<"\n";
        	pth.push_back(v);
        	set<int> tmp;
        	for(int i:pth){
        		for(int j:adj[i]){
        			tmp.insert(j);
        		}
        	}
        	for(int i:pth){
        		tmp.erase(i);
        	}
        	for(int i:tmp){
        		for(int j:pth){
        			adj[i].erase(j);
        		}
        	}
        	for(int i:pth){
        		adj[i].clear();
        	}
        	adj[v].swap(tmp);
        	for(int i:adj[v]){
        		adj[i].insert(v);
        	}
        	solve();
        }
        int main(){
        	ios_base::sync_with_stdio(false);
        	cin.tie(0);
        	cout.tie(0);
        	cin>>n;
        	for(int i=1;i<n;i++){
        		int u,v;
        		cin>>u>>v;
        		adj[u].insert(v);
        		adj[v].insert(u);
        	}
        	int d1s=0;
        	for(int i=1;i<=n;i++){
        		if(adj[i].size() == 1)d1s++;
        	}
        	cout<<((d1s+1)/2)<<"\n";
        	solve();
        	return 0;
        }

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

net.cpp: In function 'void solve()':
net.cpp:86:49: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |          cout<<gtlf(ind1,v)<<" "<<gtlf(ind2,v)<<"\n";
      |                                                 ^~~~

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