제출 #550815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550815		Bobonbush	Network (BOI15_net)	C++17	0 / 100	1 ms	340 KiB

net

#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if(x == -1 || x >y)
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */
const int N = 5e5+1;
int n , deg[N] ;
int depth[N];
class GRAPH
{
    private:
        vector<vector<int>>vertices;

    public :
        GRAPH(int _n)
        {
            vertices.resize(_n+1);
        }

        void AddEdge(int u ,int v)
        {
            vertices[u].push_back(v);
            vertices[v].push_back(u);
        }

        void DFS(int u ,int daddy)
        {
            foreach(int v in vertices[u])
            {
                if(v == daddy)
                {
                    continue;
                }
                depth[v] = depth[u] + 1;
                DFS(v , u);
            }
        }
};

int u ,v;
int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    cin >> n;
    GRAPH graph(n);
    for(int i = 1; i <= n-1 ; i++)
    {
        cin >> u >> v;
        graph.AddEdge(u , v);
        deg[u]++;
        deg[v]++;
    }
    vector<int>Leaves;
    for(int i = 1; i <= n ; i++)
    {
        if(deg[i] == 1)
        {
            Leaves.push_back(i);
        }
    }
    cout << (((int)Leaves.size()) >> 1 ) + (((int)Leaves.size()) & 1)  <<'\n';

    graph.DFS(1 , -1);

    sort(Leaves.begin() , Leaves.end() , [] (int &x , int &y)
         {
             return depth[x] < depth[y];
         });

    for(int i = 0,   j = (int)Leaves.size()-1 ; j > i ; i++ , j-- )
    {
        cout << Leaves[i] << ' ' << Leaves[j] <<'\n';
    }
    if(((int)Leaves.size()) & 1)
    {
        cout << 1 << ' ' << Leaves[(((int)Leaves.size()) >> 1) ];
    }

    return 0;
}

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