# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
605042 | 2022-07-25T12:30:15 Z | tamthegod | Network (BOI15_net) | C++14 | 16 ms | 23864 KB |
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n; vector<int> adj[maxN]; void ReadInput() { cin >> n; for(int i=1; i<n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } } void Solve() { vector<int> leaf; for(int i=1; i<=n; i++) { if(adj[i].size() == 1) leaf.pb(i); } if(leaf.size() % 2 == 0) { cout << leaf.size() / 2 << '\n'; for(int i=0; i<leaf.size(); i+=2) cout << leaf[i] << " " << leaf[i + 1] << '\n'; return; } cout << leaf.size() / 2 + 1 << '\n'; for(int i=0; i<leaf.size()-1; i+=2) cout << leaf[i] << " " << leaf[i + 1] << '\n'; for(int i=1; i<=n; i++) { if(i != adj[leaf.back()][0]) { cout << leaf.back() << " " << i; return; } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 23764 KB | Output is correct |
2 | Correct | 13 ms | 23808 KB | Output is correct |
3 | Correct | 13 ms | 23864 KB | Output is correct |
4 | Correct | 14 ms | 23816 KB | Output is correct |
5 | Correct | 16 ms | 23760 KB | Output is correct |
6 | Correct | 13 ms | 23764 KB | Output is correct |
7 | Correct | 13 ms | 23796 KB | Output is correct |
8 | Correct | 14 ms | 23816 KB | Output is correct |
9 | Correct | 13 ms | 23764 KB | Output is correct |
10 | Incorrect | 15 ms | 23764 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 23764 KB | Output is correct |
2 | Correct | 13 ms | 23808 KB | Output is correct |
3 | Correct | 13 ms | 23864 KB | Output is correct |
4 | Correct | 14 ms | 23816 KB | Output is correct |
5 | Correct | 16 ms | 23760 KB | Output is correct |
6 | Correct | 13 ms | 23764 KB | Output is correct |
7 | Correct | 13 ms | 23796 KB | Output is correct |
8 | Correct | 14 ms | 23816 KB | Output is correct |
9 | Correct | 13 ms | 23764 KB | Output is correct |
10 | Incorrect | 15 ms | 23764 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 23764 KB | Output is correct |
2 | Correct | 13 ms | 23808 KB | Output is correct |
3 | Correct | 13 ms | 23864 KB | Output is correct |
4 | Correct | 14 ms | 23816 KB | Output is correct |
5 | Correct | 16 ms | 23760 KB | Output is correct |
6 | Correct | 13 ms | 23764 KB | Output is correct |
7 | Correct | 13 ms | 23796 KB | Output is correct |
8 | Correct | 14 ms | 23816 KB | Output is correct |
9 | Correct | 13 ms | 23764 KB | Output is correct |
10 | Incorrect | 15 ms | 23764 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |