Submission #1173719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173719		ThommyDB	Network (BOI15_net)	C++20	0 / 100	0 ms	328 KiB

net

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> adj, rootAdjLeafs;

int rootAdj = 0;
int dfs(int x, int prev){
    if(adj[x].size()==1){
        //cout << "x: "<< x+1<<"\n";
        rootAdjLeafs[rootAdj].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;
        }
    }
    rootAdjLeafs.resize(adj[root].size());
    for(int i = 0; i < adj[root].size(); i++){
        //cout << "begin: " << adj[root][i] << "\n";
        rootAdj = i;
        dfs(adj[root][i], root);
    }
    /*cout << "root: " << root << "\n";
    for(int i = 0; i < rootAdjLeafs.size(); i++){
        cout << "leaf size: " << rootAdjLeafs[i].size() << "\n";
    }*/
    vector<pair<int, int>> ans;
    for(int i = 0; i < rootAdjLeafs.size()-1; i++){
        for(int j = rootAdjLeafs[i].size()-1; j >= 0; j--){
            int largestSize = i+1;
            for(int k = i+2; k < rootAdjLeafs.size(); k++){
                if(rootAdjLeafs[k].size() > rootAdjLeafs[largestSize].size()){
                    largestSize = k;
                }
            }
            if(rootAdjLeafs[largestSize].size()==0){
                ans.push_back({rootAdjLeafs[i][j], root});
            }
            else{
                ans.push_back({rootAdjLeafs[i][j], rootAdjLeafs[largestSize].back()});
                rootAdjLeafs[largestSize].pop_back();
            }
            rootAdjLeafs[i].pop_back();
        }
    }
    for(int i = 0; i < rootAdjLeafs.back().size(); i++){
        ans.push_back({rootAdjLeafs.back()[i], root});
    }
    cout << ans.size() << "\n";
    for(auto u : ans){
        cout << u.first+1 << " " << u.second+1 << "\n";
    }
}

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