Submission #23655903

---

Source Code Expand

#include <bits/stdc++.h>
#include "animals.h"

using namespace std;

using vi = vector<int>;
#define eb emplace_back

#define FOR(i, n) for (int i = 0; (i) < (int)(n); ++(i))
#define FOR3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i))
#define FOR_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i))
#define FOR3_R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i))
#define all(x) x.begin(), x.end()

template <typename T>
struct Edge {
  int frm, to;
  T cost;
  int id;
  Edge(int a, int b, T c, int d) : frm(a), to(b), cost(c), id(d) {}
};

template <typename T>
struct Graph {
  int N, M;
  using edge_t = Edge<T>;
  vector<edge_t> edges;
  vector<vector<edge_t>> G;
  bool directed;
  Graph(int N, bool bl = false) : N(N), M(0), G(N), directed(bl) {}

  void add_edge(int frm, int to, T cost = 1) {
    auto e = edge_t(frm, to, cost, M);
    edges.eb(e);
    G[frm].eb(e);
    if (!directed) {
      auto e_rev = edge_t(to, frm, cost, M);
      G[to].eb(e_rev);
    }
    ++M;
  }

  vector<edge_t>& operator[](int v) { return G[v]; }
};

vi comp;  // 頂点 → 成分
vector<int> comp_size;
multiset<int> sz;
vector<bool> deleted;  // 削除済の辺
Graph<int> G(1 << 17);

void init(int N, int E[][2]) {
  comp.resize(N);
  deleted.resize(N - 1);
  FOR(i, N - 1) {
    auto a = E[i][0];
    auto b = E[i][1];
    G.add_edge(a, b);
  }
  sz.insert(N);
  comp_size.eb(N);
}

void rm_edge(Edge<int>& e) {
  deleted[e.id] = true;
  int u = e.frm, v = e.to;
  // 小さい連結成分を手に入れたい
  auto small_comp = [&]() -> vi {
    struct T {
      int v;
      int nxt;
      int ng;
    };
    vector<T> dfs[2];
    vi C[2];
    dfs[0].eb(T({u, 0, v}));
    dfs[1].eb(T({v, 0, u}));
    C[0].eb(u);
    C[1].eb(v);
    for (int t = 0;; t ^= 1) {
      if (dfs[t].empty()) return C[t];
      T data = dfs[t].back();
      dfs[t].pop_back();
      if (data.nxt == G[data.v].size()) continue;
      auto e = G[data.v][data.nxt];
      dfs[t].eb(T({data.v, data.nxt + 1, data.ng}));
      if (deleted[e.id]) continue;
      if (e.to == data.ng) continue;
      dfs[t].eb(T({e.to, 0, e.frm}));
      C[t].eb(e.to);
    }
  };

  auto C = small_comp();
  int c = comp[u];
  int new_c = comp_size.size();
  int sz1 = comp_size[c];
  int sz2 = C.size();
  int sz3 = sz1 - sz2;

  sz.erase(sz.find(sz1));
  sz.insert(sz2);
  sz.insert(sz3);

  comp_size.eb(sz2);
  comp_size[c] = sz3;
  for (auto&& v : C) {
    comp[v] = new_c;
  }
}

int query(int v) {
  for (auto&& e : G[v]) {
    if (deleted[e.id]) continue;
    rm_edge(e);
  }
  return *(--sz.end());
  // return 1;
}

Submission Info

Compile Error

./grader.cpp: In function ‘int main()’:
./grader.cpp:15:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   15 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
./grader.cpp:17:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d%d", &(E[i][0]), &(E[i][1]));
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./grader.cpp:22:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~

Judge Result