제출 #1282800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282800		Faisal_Saqib	Network (BOI15_net)	C++20	0 / 100	3 ms	332 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
vector<int> ma[N];
// vector<int> cur;
vector<pair<int,int>> ans,cur;
void dfs(int x,int p=-1,int h=1)
{
    bool leaf=1;
    for(auto y:ma[x])
    {
        if(y==p)continue;
        leaf=0;
        dfs(y,x,h+1);
    }
    if(leaf)
    {
        cur.push_back({h,x});
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        ma[x].push_back(y);
        ma[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(ma[i].size()==1)
        {
            cur.push_back({i,1});
            dfs(i);
            sort(begin(cur),end(cur));
            int sz=cur.size();
            for(int j=0;j<=sz-1-j;j++)
            {
                if(j==sz-1-j)
                {
                    ans.push_back({cur[j].second,i});
                    break;
                }
                ans.push_back({cur[j].second,cur[sz-1-j].second});
            }
            // i,n-i-1
            break;
        }
    }

    cout<<ans.size()<<endl;
    for(auto i:ans)
    {
        cout<<i.first<<' '<<i.second<<endl;
    }
}

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