Submission #394760

#	Time	Username	Problem	Language	Result	Execution time	Memory
394760		mp007mp	Network (BOI15_net)	C++14	18 / 100	2070 ms	2124 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(){
	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:85:41: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  cout<<gtlf(ind1,v)<<" "<<gtlf(ind2,v)<<"\n";
      |                                         ^~~~

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