Submission #1128891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128891		ntdaccode	Network (BOI15_net)	C++20	0 / 100	16 ms	23876 KiB

net

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;

int n;
vector<int> ke[M], node;
//vector<ii> ans;
//namespace trace
//{
//  bool d[M];
//  void check()
//  {
//    for(ii v : ans) {
//      ke[v.first].pb(v.second);
//      ke[v.second].pb(v.first);
//    }
//    for(int i = 1;i <= n; i++) {
//        d[i] = false;
//    }
//    queue<int> q;
//    d[1] = true;
//    q.push(1);
//    while(!q.empty()) {
//      int u = q.front(); q.pop();
//      for(int v : ke[u]) {
//        if(!d[v]) {
//          d[v] = true;
//          q.push(v);
//        }
//      }
//    }
//    bool ok = 1;
//    for(int i = 1;i <= n; i++) if(!d[i]) ok = 0;
//    assert(ok);
//  }
//
//}

void dfs(int u,int p = 0)
{
  int chk = 0;
  for(int v : ke[u]) {
    if(v == p) continue;
    chk++;
    dfs(v,u);
  }
  if(chk == 1 && u == 1) node.pb(u);
  if(chk == 0) node.pb(u);
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  if(fopen("1.inp","r")) {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }

  #define task ""
  if(fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n;
  for(int i = 1;i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    ke[u].pb(v);
    ke[v].pb(u);
  }
  dfs(1,0);
  cout << (node.size() + 1)/2 << "\n";
  for(int i = 0;i < node.size() - 1; i+= 2) {
    cout << node[i]  << " " << node[i + 1] << "\n";
    //ans.pb({node[i], node[i + 1]});

  }
  if(node.size() % 2 == 1) {
      cout << node[0] << " " << node.back() << "\n";
      //ans.pb({node[0], node.back()});
  }

  //trace :: check();


}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
net.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
net.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
net.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
net.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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