# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
910031 | Petrix | Network (BOI15_net) | C++17 | 1 ms | 2392 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> v;
int frunza[500001],p[500001];
vector<pair<int,int>> rasp;
int cnt;
void dfs(int parinte,int nod){
p[nod]=cnt;cnt++;
int aux=0,i;
for(i=0;i<v[nod].size();i++){
if(v[nod][i]!=parinte){
dfs(nod,v[nod][i]);
aux++;
}
}
if(!aux) frunza[nod]=1;
}
int main()
{
int n,i,a,b;cnt=0;
cin>>n;v.resize(n+1);
for(i=0;i<n-1;i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(-1,1);
for(i=1;i<=n;i++){
if(i==1 || frunza[i])
rasp.push_back({p[i],i});
}
cout<<(rasp.size()+1)/2<<"\n";
sort(rasp.begin(),rasp.end());
for(i=0;i<(rasp.size()+1)/2;i++){
cout<<rasp[i].second<<" "<<rasp[i+(rasp.size()/2)].second<<"\n";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |