Submission #1282807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282807		Faisal_Saqib	Network (BOI15_net)	C++20	0 / 100	3 ms	14636 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});
        // if(cur.size())
        // {
        //     ans.push_back({cur.back(),x});
        //     cur.pop_back();
        // }
        // else
        // {
        //     cur.push_back(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({1,i});
            dfs(i);
            // if(cur.size()%2==1)
            // {
            //     cur.push_back({1,i});
            // }
            sort(begin(cur),end(cur));
            int sz=cur.size();
            int k=sz/2;
            // 0 1 2 3 sz=4
            // 2
            // 0 2 
            // 1 3
            // 0 1 2
            // sz=3
            // 
            for(int j=0;j<sz;j++)
            {
                if(j+k>=sz)
                {if(ans.size()<(sz+1)/2)
                    {
                    ans.push_back({cur[j].second,i});

                    }
                    break;
                }
                // if(j==sz-1-j)
                // {
                //     break;
                // }
                ans.push_back({cur[j].second,cur[j+k].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