# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
748400 | 2023-05-26T08:25:29 Z | mariowong | Network (BOI15_net) | C++14 | 1 ms | 2644 KB |
#include <bits/stdc++.h> using namespace std; int t; vector <int> edge[100005]; int dis[100005]; bool vis[100005],ok[100005]; void dfs(int x,int d){ vis[x]=true; dis[x]=d; for (int i=0;i<edge[x].size();i++){ if (!vis[edge[x][i]]) dfs(edge[x][i],d+1); } } void dfs3(int x,int d){ ok[x]=true; for (int i=0;i<edge[x].size();i++){ if (dis[edge[x][i]] == d-1){ dfs3(edge[x][i],d-1); break; } } } int main(){ ios::sync_with_stdio(false); int n; cin >> n; for (int i=1;i<n;i++){ int u,v; cin >> u >> v; edge[u].push_back(v); edge[v].push_back(u); } dfs(1,0); for (int i=1;i<=n;i++) vis[i]=false; int node=1; for (int i=1;i<=n;i++){ if (dis[i] > dis[node]) node=i; } dfs(node,0); node=1; for (int i=1;i<=n;i++){ if (dis[i] > dis[node]) node=i; } dfs3(node,dis[node]); cout << n-dis[node]-1 << "\n"; for (int i=1;i<=n;i++){ if (!ok[i]){ cout << node << " " << i << "\n"; node=i; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2644 KB | Invalid number of links. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2644 KB | Invalid number of links. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2644 KB | Invalid number of links. |
2 | Halted | 0 ms | 0 KB | - |