Submission #709619

#	Time	Username	Problem	Language	Result	Execution time	Memory
709619		ToroTN	Network (BOI15_net)	C++14	100 / 100	639 ms	54052 KiB

net

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
int n,a,b,id[500005],root,num,a1,b1,a2,b2;
vector<int> v[500005],leaf;
vector<pair<int,int> > ans;
void dfs(int u,int p)
{
    for(auto node:v[u])
    {
        if(node==p)continue;
        dfs(node,u);
    }
    if(v[u].size()==1)leaf.pb(u);
}
int main()
{
    cin>> n;
    for(int i=1;i<n;i++)
    {
        cin >> a >> b;
        ++id[a],++id[b];
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(id[i]>1)
        {
            root=i;
            break;
        }
    }
    for(auto node:v[root])
    {
        num=node;
        dfs(node,root);
    }
    if(leaf.size()%2==0)
    {
        for(int i=0;i<leaf.size()/2;i++)
        {
            ans.pb({leaf[i],leaf[i+leaf.size()/2]});
        }
    }else
    {
        for(int i=0;i<leaf.size()/2;i++)
        {
            ans.pb({leaf[i],leaf[i+leaf.size()/2+1]});
        }
        ans.pb({leaf[leaf.size()/2],root});
    }
    printf("%d\n",ans.size());
    for(auto [x,y]:ans)
    {
        printf("%d %d\n",x,y);
    }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i=0;i<leaf.size()/2;i++)
      |                     ~^~~~~~~~~~~~~~
net.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i=0;i<leaf.size()/2;i++)
      |                     ~^~~~~~~~~~~~~~
net.cpp:55:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
   55 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |             %ld
net.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [x,y]:ans)
      |              ^

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