Submission #394764

#	Time	Username	Problem	Language	Result	Execution time	Memory
394764		mp007mp	Network (BOI15_net)	C++14	63 / 100	257 ms	5880 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 = 2005;
    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;
    }

Compilation message (stderr)

net.cpp: In function 'void solve()':
net.cpp:86:45: 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