Submission #1173727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173727		ThommyDB	Network (BOI15_net)	C++20	100 / 100	459 ms	47752 KiB

net

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> adj;
vector<int> allLeaves;

int dfs(int x, int prev){
    if(adj[x].size()==1){
        //cout << "x: "<< x+1<<"\n";
        allLeaves.push_back(x);
        return 1;
    }

    int cnt = 0;
    for(auto u : adj[x]){
        if(u==prev)continue;
        //cout << "for " << x+1 << ": " << u+1 << "\n";
        cnt+=dfs(u, x);
    }
    return cnt;
}

signed main(){
    cin >> n;
    adj.resize(n);
    int root = 0;
    for(int i = 0; i < n-1; i++){
        int u, v;
        cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if(adj[u].size()>adj[root].size()){
            root = u;
        }
        if(adj[v].size()>adj[root].size()){
            root = v;
        }
    }
    for(int i = 0; i < adj[root].size(); i++){
        //cout << "begin: " << adj[root][i] << "\n";
        dfs(adj[root][i], root);
    }
    /*for(int i = 0; i < allLeaves.size(); i++){
        cout << allLeaves[i] << "\n";
    }*/
    vector<pair<int, int>> ans;
    for(int i = 0; i < (allLeaves.size()+(allLeaves.size()%2))/2; i++){
        int connectLeave = allLeaves[(i+(allLeaves.size()+(allLeaves.size()%2))/2)%(allLeaves.size())];
        ans.push_back({allLeaves[i], connectLeave});
    }
    cout << ans.size() << "\n";
    for(auto u : ans){
        cout << u.first+1 << " " << u.second+1 << "\n";
    }
}

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