oj.uz

Submission #107194

# Submission time Handle Problem Language Result Execution time Memory
107194 2019-04-22T12:15:50 Z dolphingarlic Network (BOI15_net) C++17
0 / 100
 13 ms 12160 KB 
#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 << endl;
    FOR(i, 0, (ll)(leaves.size() / 2)) cout << leaves[i] << ' ' << leaves[leaves.size() - i - 1] << endl;
    if (leaves.size() & 1) cout << leaves[leaves.size() / 2] << " 1" << endl;
    return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12008 KB Output is correct
2 Incorrect 13 ms 12160 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12008 KB Output is correct
2 Incorrect 13 ms 12160 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12008 KB Output is correct
2 Incorrect 13 ms 12160 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -