Submission #107190

#	Time	Username	Problem	Language	Result	Execution time	Memory
107190		dolphingarlic	Network (BOI15_net)	C++14	0 / 100	15 ms	12160 KiB

net

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for(ll i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<ll> graph[500001], leaves;

void dfs(ll node, ll parent = 0) {
    if (graph[node].size() == 1) leaves.push_back(node);
    for (auto& i : graph[node]) {
        if (i == parent) continue;
        dfs(i, node);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    FOR(i, 0, n - 1) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1);
    cout << (leaves.size() + 1) / 2 << '\n';
    FOR(i, 0, leaves.size() / 2) cout << leaves[i] << ' ' << leaves[leaves.size() - i - 1] << '\n';
    if (leaves.size() & 1) cout << leaves[leaves.size() / 2] << " 1\n";
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:3:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for(ll i = x; i < y; i++)
net.cpp:30:9:
     FOR(i, 0, leaves.size() / 2) cout << leaves[i] << ' ' << leaves[leaves.size() - i - 1] << '\n';
         ~~~~~~~~~~~~~~~~~~~~~~~       
net.cpp:30:5: note: in expansion of macro 'FOR'
     FOR(i, 0, leaves.size() / 2) cout << leaves[i] << ' ' << leaves[leaves.size() - i - 1] << '\n';
     ^~~

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