Submission #748398

#TimeUsernameProblemLanguageResultExecution timeMemory
748398mariowongNetwork (BOI15_net)C++14
0 / 100
2 ms2644 KiB
#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){ vis[x]=true; t=x; for (int i=0;i<edge[x].size();i++){ if (!vis[edge[x][i]]) dfs(edge[x][i]); } } void dfs2(int x,int d){ vis[x]=true; dis[x]=d; for (int i=0;i<edge[x].size();i++){ if (!vis[edge[x][i]]) dfs2(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); for (int i=1;i<=n;i++) vis[i]=false; dfs2(t,0); int 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 (stderr)

net.cpp: In function 'void dfs(int)':
net.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for (int i=0;i<edge[x].size();i++){
      |               ~^~~~~~~~~~~~~~~
net.cpp: In function 'void dfs2(int, int)':
net.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i=0;i<edge[x].size();i++){
      |               ~^~~~~~~~~~~~~~~
net.cpp: In function 'void dfs3(int, int)':
net.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i=0;i<edge[x].size();i++){
      |               ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...