Submission #553371

#	Time	Username	Problem	Language	Result	Execution time	Memory
553371		new_acc	Network (BOI15_net)	C++14	100 / 100	673 ms	63756 KiB

net

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
vi graf[N],l;
void dfs(int v,int o){
	for(auto u:graf[v]){
		if(u==o) continue;
		dfs(u,v);
	}
	if(graf[v].size()==1) l.push_back(v);
}
void solve(){
	int n;
	cin>>n;
	for(int a,b,i=1;i<n;i++){
		cin>>a>>b;
		graf[a].push_back(b),graf[b].push_back(a);
	}
	dfs(1,1);
	cout<<((l.size()+1)>>1)<<"\n";
	for(int i=0;i<(l.size())>>1;i++) cout<<l[i]<<" "<<l[i+(l.size()>>1)]<<"\n";
	if(l.size()&1) cout<<l[l.size()-1]<<" "<<l[l.size()>>1]<<"\n";
}
int main(){
	solve();
}

Compilation message (stderr)

net.cpp: In function 'void solve()':
net.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<(l.size())>>1;i++) cout<<l[i]<<" "<<l[i+(l.size()>>1)]<<"\n";
      |              ~^~~~~~~~~~~~~~

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