Submission #1091620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091620		DeathIsAwe	Network (BOI15_net)	C++17	100 / 100	199 ms	46680 KiB

net

    #include <bits/stdc++.h>
    #define el '\n'
    #define fi first
    #define sc second
    #define int ll
    #define pii pair<int, int>
    #define all(v) v.begin(), v.end()
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    using namespace std;
    using ll=long long;
    using ull=unsigned long long;
    using ld=long double;
    const int mod=1e9+7;
    const int N=5e5+11;
    int n, root;
    vector<int> adj[N], leaf;
    void dfs(int u, int pa)
    {
        if(adj[u].size()==1) leaf.push_back(u);
        for(int v:adj[u])
        {
            if(v!=pa) dfs(v, u);
        }
    }
    void sol()
    {
        cin >> n;
        for(int i=1;i<n;i++)
        {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        for(int i=1;i<=n;i++) if(adj[i].size()>1) root=i;
        dfs(root, 0);
        int sz=leaf.size();
        cout << (sz+1)/2 << el;
        for(int i=0; i<(sz+1)/2; i++) cout << leaf[i] << ' ' << leaf[i + sz / 2] << el;
    }
    signed main()
    {
    //    freopen("divisor.INP", "r", stdin);
    //    freopen("divisor.OUT", "w", stdout);
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int t=1;
        //cin >> t;
        while(t--)
        {
            sol();
        }
    }

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