Submission #1188988

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

net

// YoruoniVamp - VTUBE
// Pragma Credit to Discord: pxsithexahydride
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,no-stack-protector,inline-small-functions,inline,unsafe-math-optimizations,omit-frame-pointer,inline-functions-called-once")
#include <bits/stdc++.h>
#pragma GCC target("avx2,fma,popcnt,lzcnt,bmi,bmi2,sse4.2,tune=native")
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define ull unsigned ll
#define cint const int
#define cf const float

cint mxA = 1e6+5, MOD = 1e9+7, INF = 0x3f3f3f3f;
cint d4x[4] = {0, 1, 0, -1}, d4y[4] = {1, 0, -1, 0};
cint d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

void wait(int ms){
    clock_t endwait;
    endwait = clock() + ms;
    while(clock()<endwait){}
}

int findPar(int u, vector<int> &parent){return (parent[u]==u?u:parent[u]=findPar(parent[u],parent));}

void solve(){
    int n; cin >> n;
    vector<ll> deg(n+1,0);
    ll mn = INT_MAX;
    for(int i = 1; i <= n-1; i++){
        ll a, b; cin >> a >> b;
        deg[a]++; deg[b]++;
    }
    vector<int> edge;
    for(int i = 1; i <= n; i++){
        if(deg[i]==1) edge.emplace_back(i);
    }
    vector<pair<int,int>> ans;
    while(edge.size()>1){
        ans.emplace_back(edge[0],edge[1]);
        edge.erase(edge.begin());
        edge.erase(edge.begin());
    }if(edge.size()) ans.emplace_back(1,edge[0]);
    cout << ans.size() << endl;
    for(auto [a,b]: ans) cout << a << ' ' << b << endl;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

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