Submission #605113

#TimeUsernameProblemLanguageResultExecution timeMemory
605113tamthegodNetwork (BOI15_net)C++14
100 / 100
467 ms68408 KiB
#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]; int depth[maxN]; vector<int> leaf; 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 dfs(int u, int par) { if(adj[u].size() == 1) leaf.pb(u); for(int v : adj[u]) { if(v == par) continue; depth[v] = depth[u] + 1; dfs(v, u); } } void Solve() { dfs(1, 0); int l = 0, step = leaf.size() / 2; if(leaf.size() % 2 == 0) { cout << leaf.size() / 2 << '\n'; while(l + step < leaf.size()) { cout << leaf[l] << " " << leaf[l + step] << '\n'; l++; } return; } leaf.pb(leaf[0]); step++; cout << leaf.size() / 2 << '\n'; while(l + step < leaf.size()) { cout << leaf[l] << " " << leaf[l + step] << '\n'; l++; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }

Compilation message (stderr)

net.cpp: In function 'void Solve()':
net.cpp:47:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while(l + step < leaf.size())
      |               ~~~~~~~~~^~~~~~~~~~~~~
net.cpp:57:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while(l + step < leaf.size())
      |           ~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...