Submission #1332492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332492		Warinchai	Network (BOI15_net)	C++20	0 / 100	1 ms	344 KiB

net

#include<bits/stdc++.h>
using namespace std;

vector<int>adj[500005];
int sz[500005];
vector<int>v;

int dfssz(int u,int p){
    if(adj[u].size()==1)sz[u]=1;
    for(auto x:adj[u])if(x!=p)sz[u]+=dfssz(x,u);
}

int centroid(int u,int p,int rsz){
    for(auto x:adj[u])if(x!=p&&sz[x]*2>rsz)return centroid(x,u,rsz);
    return u;
}

void dfs(int u,int p){
    if(adj[u].size()==1)v.push_back(u);
    for(auto x:adj[u])if(x!=p)dfs(x,u);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int rt=0;
    dfs(rt=centroid(1,0,dfssz(1,0)),0);
    vector<pair<int,int>>ans;
    for(int i=0;i<v.size()/2;i++){
        int add=v.size()-v.size()/2;
        ans.push_back({v[i],v[i+add]});
    }
    if(v.size()%2==1)ans.push_back({v[v.size()/2],rt});
    cout<<ans.size()<<'\n';
    for(auto x:ans)cout<<x.first<<' '<<x.second<<"\n";
}

Compilation message (stderr)

net.cpp: In function 'int dfssz(int, int)':
net.cpp:11:1: warning: no return statement in function returning non-void [-Wreturn-type]
   11 | }
      | ^

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