Submission #1127906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127906		VinhLuu	Network (BOI15_net)	C++20	0 / 100	17 ms	23872 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

//#define int long long

const int N = 1e6 + 5;

int n, a[N];
vector<int> p[N];

int ans = 0, f[N], g[N], pa[22][N], in[N], en[N], demin;

void pre(int u,int v) {
  in[u] = ++demin;
  for(int j = 1; j <= 20; j ++) pa[j][u] = pa[j - 1][pa[j - 1][u]];
  for(auto j : p[u]) if(j != v) {
    pa[0][j] = u;
    pre(j, u);
  }
  en[u] = demin;
}

bool kt(int u,int v) {
  return in[u] <= in[v] && in[v] <= en[u];
}

int LCA(int u,int v) {
  if(kt(u, v)) return u;
  int kq = u;
  for(int i = 20; i >= 0; i --) if(kt(pa[i][u], v)) kq = pa[i][u];
  else u = pa[i][u];
  return kq;
}

vector<pair<int,int>> kq;

void dfs(int u,int v) {
  if((int)p[u].size() == 1 && u != 1) {
    f[u] = u;
    ans++;
    return;
  }

  for(auto j : p[u]) if(j != v) {
    dfs(j, u);
    if(!f[u]) {
      f[u] = f[j];
      g[u] = g[j];
      continue;
    }
    if(!g[u]) {
      if(g[j]) {
        kq.push_back({f[u], f[j]});
        ans--;
        f[u] = g[j];
      } else {
        g[u] = f[j];
      }
    } else {
      kq.push_back({f[j], g[u]});
      g[u] = g[j];
      ans--;
    }
  }
  if(u == 1) {
    if(g[u]) {
      if(LCA(g[u], f[u]) == u) {
        ans--;
        kq.push_back({g[u], f[u]});
      } else {
        kq.push_back({u, f[u]});
        kq.push_back({u, g[u]});
      }
    } else {
      kq.push_back({u, f[u]});
    }
  }
  cerr << u << " " << f[u] << " " << g[u] << "\n";
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n;
  for(int i = 1; i < n; i ++) {
    int x, y; cin >> x >> y;
    p[x].push_back(y);
    p[y].push_back(x);
  }

  dfs(1, 0);

  cout << ans << "\n";
  for(auto [x, y] : kq) cout << x << " " << y << "\n";

}
#endif // lpv

Compilation message (stderr)

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

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