Submission #821991

#	Time	Username	Problem	Language	Result	Execution time	Memory
821991		exodus_	Network (BOI15_net)	C++14	100 / 100	794 ms	47592 KiB

net

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int nmax = 500005;
vector<int>adj[nmax];
vector<int>leaf;
void DFS() {
    stack<pair<int,int>>st;
    st.push({1,0});
    while(!st.empty()) {
        int nod = st.top().fi;
        int par = st.top().se;
        st.pop();
        if(adj[nod].size()==1) leaf.push_back(nod);
        for(auto nxt:adj[nod]) {
            if(nxt != par) st.push({nxt,nod});
        }
    }

}
int main() {
    int n,a,b;
    cin >> n;
    for(int i=1; i<n; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DFS();
    int N = (leaf.size()+1)/2;
    cout << N << endl;
    for(int i=0; i<N; i++) {
        cout << leaf[i] << " " << leaf[i+(leaf.size()/2)] << endl;
    }
    return 0;
}

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