Submission #655830

#TimeUsernameProblemLanguageResultExecution timeMemory
655830as111Network (BOI15_net)C++14
100 / 100
573 ms47704 KiB
//simple dfs #include <vector> #include <iostream> #define MAXN 500000 #define pb push_back #define fi first #define se second using namespace std; vector<int> adj[MAXN + 5]; vector<int> leaf; void dfs(int u, int par) { if (adj[u].size() == 1) leaf.pb(u); for (int v : adj[u]) { if (v == par) continue; dfs(v, u); } } void Solve() { dfs(1, 0); int l = 0, step = (int)(leaf.size() / 2); if (leaf.size() % 2 == 0) { cout << leaf.size() / 2 << '\n'; while (l + step < (int)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++; } } int main() { int N; cin >> N; for (int i = 1; i < N; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } Solve(); }

Compilation message (stderr)

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