Submission #1091619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091619		DeathIsAwe	Network (BOI15_net)	C++17	100 / 100	198 ms	37700 KiB

net

#include <bits/stdc++.h>
using namespace std;
bool visited[500000];
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, d1,d2; cin >> n;
    vector<vector<int>> graph(n);
    for (int i=0;i<n-1;i++) {
        cin >> d1 >> d2; d1--; d2--;
        graph[d1].push_back(d2);
        graph[d2].push_back(d1);
        visited[i] = false;
    }
    visited[n - 1] = false;

    
    vector<int> leaves;
    stack<int> dfs; dfs.push(0);
    int node;
    bool flag;
    if (graph[0].size() == 1) {leaves.push_back(0);}
    while (dfs.size() > 0) {
        flag = false;
        node = dfs.top(); dfs.pop();
        visited[node] = true;
        for (int i: graph[node]) {
            if (!visited[i]) {
                dfs.push(i);
                flag = true;
            }
        }
        if (!flag) {
            leaves.push_back(node);
        }
    }


    int m = leaves.size();
    cout << (m + 1) / 2 << '\n';
    for (int i=0;i<m/2;i++) {
        cout << leaves[i]  + 1 << ' ' << leaves[i + (m / 2)] + 1 << '\n';
    }
    if (m % 2 == 1) {
        cout << leaves[m - 1] + 1 << ' ' << leaves[m - 1 - (m / 2)] + 1 ;
    }
}

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