Submission #638420

#	Time	Username	Problem	Language	Result	Execution time	Memory
638420		xad	Network (BOI15_net)	C++14	100 / 100	553 ms	63100 KiB

net

#include <bits/stdc++.h>
using namespace std ;
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define intt int t; cin>>t; while(t--)
#define emp emplace_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
//#define a first
//#define b second
typedef long long ll;
vector<int>v;
void dfs(int i, int p, vector<int>adj[])
{
    if(sz(adj[i])==1){v.emp(i); return ;}
    for(auto j:adj[i])
        if(j!=p)dfs(j,i,adj);
}
void mxx(int i, int p, vector<int>adj[], int&ind ,int&mx, int dis=0)
{
    if(sz(adj[i])==1&&i!=ind)
    {
        if(dis>mx)ind=i,mx=dis; return ;
    }
    for(auto j:adj[i])
        if(j!=p)mxx(j,i,adj, ind, mx, dis+1);
}
int main()
{

    x_x
int n; cin>>n; vector<int>adj[n+2]; for(int i=1,x,y; i<n;i++)cin>>x>>y, adj[x].emp(y), adj[y].emp(x);
int mx=0,ind=1;
for(int i=1; i<=n; i++)if(sz(adj[i])>mx)mx=sz(adj[i]), ind=i;

dfs(ind,0,adj);
cout<<(sz(v)+1)/2<<nn;
for(int i=0; i<sz(v)/2; i++)cout<<v[i]<<' '<<v[i+(sz(v)/2)]<<nn;
if(sz(v)%2)
{
  ind=mx=0;  cout<<v.back()<<' '; ind=v.back(); mxx(v.back(),0,adj,ind,mx); cout<<ind;
}
return 0;
}

Compilation message (stderr)

net.cpp: In function 'void mxx(int, int, std::vector<int>*, int&, int&, int)':
net.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |         if(dis>mx)ind=i,mx=dis; return ;
      |         ^~
net.cpp:24:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |         if(dis>mx)ind=i,mx=dis; return ;
      |                                 ^~~~~~

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