Submission #709614

#	Time	Username	Problem	Language	Result	Execution time	Memory
709614		ToroTN	Network (BOI15_net)	C++14	0 / 100	14 ms	23788 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[500005];
priority_queue<pair<int,int> > pq;
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[num].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);
    }
    for(auto node:v[root])
    {
        pq.push({leaf[node].size()-1,node});
    }
    /*while(!pq.empty())
    {
        printf("%d %d\n",pq.top().Y,pq.top().X);
        pq.pop();
    }
    return 0;*/
    while(pq.size()>0)
    {
        if(pq.size()==1)
        {
            if(pq.top().X==0)
            {
                ans.pb({root,leaf[pq.top().Y][pq.top().X]});
                break;
            }else
            {
                // printf("%d\n",ans.size());
                // for(int i=0;i<ans.size();i++)
                // {
                //     printf("%d %d\n",ans[i].X,ans[i].Y);
                // }
                // printf("\n");
                // while(!pq.empty())
                // {
                //     printf("%d %d\n",pq.top().X,pq.top().Y);
                //     pq.pop();
                // }
                // break;
                ans.pb({leaf[pq.top().Y][pq.top().X],leaf[pq.top().Y][pq.top().X-1]});
                a1=pq.top().X,a2=pq.top().Y;
                pq.pop();
                if(a1-2>=0)pq.push({a1-2,a2});
            }
        }else
        {
            a1=pq.top().X,b1=pq.top().Y;
            pq.pop();
            a2=pq.top().X,b2=pq.top().Y;
            pq.pop();
            ans.pb({leaf[b1][a1],leaf[b2][a2]});
            if(a1-1>=0)pq.push({a1-1,b1});
            if(a2-1>=0)pq.push({a2-1,b2});
            /*printf("%d\n",ans.size());
            for(int i=0;i<ans.size();i++)
            {
                printf("%d %d\n",ans[i].X,ans[i].Y);
            }
            printf("\n");
            while(!pq.empty())
            {
                printf("%d %d\n",pq.top().X,pq.top().Y);
                pq.pop();
            }
            break;*/
        }
        while(pq.size()>0)
        {
            if(pq.top().X<0)
            {
                pq.pop();
            }else
            {
                break;
            }
        }
    }
    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:112:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wformat=]
  112 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type {aka long unsigned int}
      |             %ld
net.cpp:113:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |     for(auto [x,y]:ans)
      |              ^

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