Submission #1091609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091609		DeathIsAwe	Network (BOI15_net)	C++17	0 / 100	1 ms	348 KiB

net

#include <bits/stdc++.h>
using namespace std;
bool visited[500000];


int main() {
    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;


    if (n == 2) {
        cout << 1 << '\n' << 1 << ' ' << 2;
        return 0;
    } else if (n == 1) {
        cout << 0;
        return 0;
    }

    
    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:29:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
   29 |     int root, node;
      |         ^~~~

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