Submission #1270605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270605		hypersphere	Network (BOI15_net)	C++20	100 / 100	316 ms	37188 KiB

net

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
 
#define ll long long

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

const ll mod = 998244353;
const ll INF = 1e18;
const int INT_INF = 2e9;
 
long long binpow(long long base, long long power, long long mod) {
    if (base == 0) return 0;
    if (base == 1) return 1;
    if (power <= 0) return 1;
    long long multiplier = (power % 2 == 0 ? 1 : base) % mod;
    return (multiplier * binpow((base * base) % mod, power / 2, mod)) % mod;
}

ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

ll add(ll a, ll b) {return a + b;}
ll sub(ll a, ll b) {return a - b;}

const int N = 5e5 + 1;
vector<int> adj[N];

int in[N];
int timer = -1;

void dfs(int node, int prev = -1){
    in[node] = ++timer;

    for(int v : adj[node]){
        if(v == prev) continue;
        dfs(v, node);
    }
}

bool sort_by_in(int above, int below){
    return in[above] < in[below];
}

void Run(){
    int n; cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int root = -1;
    for(int i = 1; i <= n; i++){
        if(adj[i].size() == 1) continue;
        dfs(i);
        root = i;
        break;
    }

    vector<int> leaves;
    for(int i = 1; i <= n; i++) if(adj[i].size() == 1) leaves.push_back(i);
    sort(leaves.begin(), leaves.end(), sort_by_in);

    // Basically, pair leaves from different subtrees
    if(leaves.size() % 2 == 0){
        int m = leaves.size();
        cout << m / 2 << "\n";
        for(int i = 0; i < m / 2; i++){
            cout << leaves[i] << " " << leaves[i + m/2] << "\n";
        }
    }
    else{
        int m = leaves.size();
        cout << (m + 1) / 2 << "\n";
        for(int i = 0; i < m / 2; i++){
            cout << leaves[i] << " " << leaves[i + m/2 + 1] << "\n";
        }
        cout << leaves[m/2] << " " << root << "\n";
    }

}

int main(){
    //freopen("CIRSSTR.INP", "r", stdin);
    //freopen("CIRSSTR.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int test = 1;
    //cin >> test;

    // Measuring running time (breaks when manual input)
    //auto time_start = clock();
    while(test--) Run();
    //auto time_end = clock();

    //cerr << "Time taken: " << time_end - time_start << "\n";
}

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