Submission #1091612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091612		DeathIsAwe	Network (BOI15_net)	C++17	100 / 100	252 ms	37684 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;
    int root, node;
    for (int i=0;i<n;i++) {
        if (graph[i].size() > 1) {
            dfs.push(i);
            root = i;
            break;
        }
    }
    while (dfs.size() > 0) {
        node = dfs.top(); dfs.pop();
        visited[node] = true;
        for (int i: graph[node]) {
            if (!visited[i]) {
                dfs.push(i);
            }
        }
        if (graph[node].size() == 1) {
            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 ;
    }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:24:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
   24 |     int root, node;
      |         ^~~~

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