Submission #1368071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368071		SmuggingSpun	Network (BOI15_net)	C++20	100 / 100	170 ms	37176 KiB

net

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int lim = 5e5 + 5;
int n, tdfs = 0, low[lim];
vector<int>g[lim];
void dfs(int s, int p = -1){
  low[s] = ++tdfs;
  for(int& d : g[s]){
    if(d != p){
      dfs(d, s);
    }
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n;
  for(int i = 1; i < n; i++){
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  vector<int>leaf;
  for(int i = 1; i <= n; i++){
    if(g[i].size() == 1){
      leaf.push_back(i);
    }
  }
  sort(leaf.begin(), leaf.end(), [&] (int i, int j){
    return low[i] < low[j];
  });
  cout << (int(leaf.size() + 1) >> 1) << "\n";
  for(int i = 0; i < (int(leaf.size() + 1) >> 1); i++){
    cout << leaf[i] << " " << leaf[i + (int(leaf.size()) >> 1)] << "\n";
  }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:18:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37