Submission #911145

#	Time	Username	Problem	Language	Result	Execution time	Memory
911145		ttamx	Network (BOI15_net)	C++14	0 / 100	9 ms	25516 KiB

net

#include<bits/stdc++.h>

using namespace std;

const int N=5e5+5;

int n;
int sz[N];
vector<int> adj[N],vec[N];

int dfssz(int u,int p=0){
    sz[u]=(adj[u].size()<2);
    for(auto v:adj[u])if(v!=p)sz[u]+=dfssz(v,u);
    return sz[u];
}

int centroid(int u,int cnt,int p=0){
    for(auto v:adj[u])if(v!=p&&sz[v]>cnt/2)return centroid(v,cnt,u);
    return u;
}

void dfs(int u,int p,vector<int> &comp){
    if(adj[u].size()==1)comp.emplace_back(u);
    for(auto v:adj[u])if(v!=p)dfs(v,u,comp);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    int c=centroid(1,dfssz(1));
    vector<vector<int>> res;
    for(auto v:adj[c]){
        res.push_back({});
        dfs(v,c,res.back());
    }
    for(int i=0;i<res.size();i++)vec[res[i].size()].emplace_back(i);
    vector<pair<int,int>> ans;
    int p=0;
    for(int i=n/2;i>=1;i--){
        for(auto x:vec[i]){
            if(p){
                ans.emplace_back(p,res[x].back());
                p=0;
            }else{
                p=res[x].back();
            }
            res[x].pop_back();
            vec[i-1].emplace_back(x);
        }
    }
    if(p)ans.emplace_back(p,c);
    cout << ans.size() << "\n";
    for(auto [x,y]:ans)cout << x << " " << y << "\n";
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<res.size();i++)vec[res[i].size()].emplace_back(i);
      |                 ~^~~~~~~~~~~
net.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [x,y]:ans)cout << x << " " << y << "\n";
      |              ^

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