Submission #1127914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127914		VinhLuu	Network (BOI15_net)	C++17	100 / 100	798 ms	114900 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;
  if(u == 1) for(int j = 0; j <= 20; j ++) pa[j][u] = u;
  else 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--;
    }
  }
//  cerr << u << " " << f[u] << " " << g[u] << " " << LCA(g[u], f[u]) << "\n";
  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]});
    }
  }

}

int dp[N];
bool ff = true;

void sol(int u,int v) {
  for(auto j : p[u]) if(j != v) {
    sol(j, u);
    dp[u] += dp[j];
  }
  if(!dp[u] && u != 1) {
    ff = 0;
  }
}

bool check_valid() {
  for(auto ptr : kq) {
    int x, y; tie(x, y) = ptr;
    if(in[x] > in[y]) swap(x, y);
    int lca = LCA(x, y);
    dp[x]++;
    dp[y]++;
    dp[lca]--;
//    cerr << x << " " << y << " t\n";
  }
  ff = 1;
  sol(1, 0);
  if(!ff) return 0;
  else return 1;
}

#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);
  }

  pre(1, 0);

  dfs(1, 0);
//  cerr << check_valid() << " g\n";
//  assert(check_valid());
//  assert(ans == (int)kq.size());

  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:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
net.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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