Submission #45278325

---

Source Code Expand

#include <atcoder/all>
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

// clang-format off
/* accelration */
// 高速バイナリ生成
//#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// cin cout の結びつけ解除, stdioと同期しない(入出力非同期化)
// cとstdの入出力を混在させるとバグるので注意
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;

/* alias */
// type
using ull = unsigned long long;
using ll = long long;
using ld = long double;
// pair
using pii = pair<int, int>;
// vector
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vpii = vector<pii>;
// unordered set
using usi = unordered_set<int>;
using usll = unordered_set<ll>;
using uss = unordered_set<string>;

/* define short */
#define pb push_back
#define mp make_pair
#define um unordered_map
#define all(obj) (obj).begin(), (obj).end()
#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

/* REP macro */
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rep1(i, n) reps(i, 1, n + 1)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define rep1r(i,n) for(ll i=n;i>=1;i--)
#define fore(i,a) for(auto &i:a)

/* func */
inline int in_int() {int x; cin >> x; return x;}
inline ll in_ll() {ll x; cin >> x; return x;}
inline double in_double() {{double x; cin >> x; return x;}}
inline string in_str() {string x; cin >> x; return x;}
inline vll in_vll(int n) { vll x(n); rep(i,n) cin >> x[i]; return x;}
inline vvll in_grid_weight_ii0(ll n){ vvll ret(n,vll(n)); rep(i,n-1) reps(j,i+1,n){ ll t; cin >> t; ret[i][j] = t; ret[j][i] = t; } return ret;}
inline int ctoi(char c) {return c - '0';}
inline ll sum(vll a) { return accumulate(all(a),0LL);}
template <typename T>inline ll sum(set<T> a) { return accumulate(all(a),0LL);}

// vector_finder: (arg)elementを vectorの先頭から(arg)search_lengthまで先頭から検索し、boolを返す
// (arg)search_length: 走査するベクトル長の上限(先頭から何要素目までを検索対象とするか、1始まりで)
template <typename T> inline bool vector_finder(std::vector<T> vec, T element, unsigned int search_length) {
    auto itr = std::find(vec.begin(), vec.end(), element);
    size_t index = std::distance( vec.begin(), itr );
    if (index == vec.size() || index >= search_length) {return false;} else {return true;}
}
template <typename T> inline void print(const vector<T>& v, string s = " ")
{rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
template <typename T, typename S> inline void print(const pair<T, S>& p)
{cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << "\n";}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v)
{for (auto&& p : v) print(p);}
template <typename T, typename S> inline void print(const map<T, S>& m)
{for (auto&& p : m) print(p);}
// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き
template <typename T> inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;}
template <typename T> inline bool chmax(T& a, const T& b) {bool compare = a < b; if (a < b) a = b; return compare;}
// gcd lcm
// C++17からは標準実装
// template <typename T> T gcd(T a, T b) {if (b == 0)return a; else return gcd(b, a % b);}
// template <typename T> inline T lcm(T a, T b) {return (a * b) / gcd(a, b);}
// clang-format on

template <typename T> inline map<T, ull> counter(const vector<T> &x) {
  map<T, ull> m;
  fore(xi, x) {
    if (m.find(xi) == m.end()) {
      m.insert(make_pair(xi, 1));
    } else {
      m[xi] += 1;
    }
  }
  return m;
}
inline map<char, ull> counter(const string &x) {
  map<char, ull> m;
  fore(xi, x) {
    if (m.find(xi) == m.end()) {
      m.insert(make_pair(xi, 1));
    } else {
      m[xi] += 1;
    }
  }
  return m;
}

// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774
struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n = 1) : n(n), f(n + 1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i])
        continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i * i; j <= n; j += i) {
        if (!f[j])
          f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x; }
  ll minfactor(ll x) { return f[x]; }
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<pii> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0)
      return {};
    vector<pii> res(1, pii(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll, int>> factor(ll x) {
    vector<pair<ll, int>> res;
    for (int p : primes) {
      int y = 0;
      while (x % p == 0)
        x /= p, ++y;
      if (y != 0)
        res.emplace_back(p, y);
    }
    if (x != 1)
      res.emplace_back(x, 1);
    return res;
  }
};

inline vector<char> str2charvec(string s) {
  vector<char> r(s.begin(), s.end());
  return r;
}

template <typename T> inline vector<pair<T, ll>> runlength(vector<T> x) {
  vector<pair<T, ll>> r;
  ll cnt = 1;
  ll n = x.size();
  rep(i, n - 1) {
    if (x[i] == x[i + 1]) {
      cnt++;
    } else {
      r.push_back(make_pair(x[i], cnt));
      cnt = 1;
    }
    if (i == n - 2) {
      r.push_back(make_pair(x[n - 1], cnt));
    }
  }
  return r;
}

struct ModComb {
  vll fac;
  vll finv;
  ll n = 0;
  ll p = 0;

  ModComb(ll n, ll p) : n(n), p(p) {
    fac.resize(n + 1);
    finv.resize(n + 1);
    vll inv(n + 1);

    fac[0] = 1;
    fac[1] = 1;
    finv[0] = 1;
    finv[1] = 1;
    inv[1] = 1;

    for (int i = 2; i < n + 1; i++) {
      fac[i] = (fac[i - 1] * i) % p;
      inv[i] = (p - ((p / i) * inv[p % i]) % p) % p;
      finv[i] = (finv[i - 1] * inv[i]) % p;
    }
  }

  ll C(ll n, ll k) {
    if (k < 0 || n < k)
      return 0;
    return ((fac[n] * finv[n - k]) % p * finv[k]) % p;
  }

  ll P(ll n, ll k) {
    if (k < 0 || n < k)
      return 0;
    return (fac[n] * finv[k]) % p;
  }

  // n個をk箇所に振り分ける(0もあり)
  ll H(ll n, ll k) {
    if (n == 0 && k == 0)
      return 1;
    if (k <= 0 || n < 0)
      return 0;
    return C(n + k - 1, n);
  }
};

vs rot(vs t) {
  ll n = t.size();
  vs res(n, string(n, 'x'));
  rep(i, n) rep(j, n) { res[j][n - i - 1] = t[i][j]; }
  return res;
};

template <typename T> struct Acc {
  vector<T> acc;
  Acc(string v) {
    acc.resize(v.size() + 1);
    acc[0] = 0;
    rep(i, v.size()) acc[i + 1] = acc[i] + ctoi(v[i]);
  }
  Acc(vector<T> v) {
    acc.resize(v.size() + 1);
    acc[0] = 0;
    rep(i, v.size()) acc[i + 1] = acc[i] + v[i];
  }
  ll size() { return acc.size(); }
  T operator[](ll i) { return acc[i]; }
};

#define INF (ll)1e18

// using mint=atcoder::modint1000000007;
using mint = atcoder::modint998244353;

#ifdef LOCAL
#include <debug_print/debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#define dbg(...)                                                               \
  cerr << "\033[33m(line:" << __LINE__ << ") ";                                \
  debug(__VA_ARGS__);
#else
#define dbg(...) (static_cast<void>(0))
#endif

int main() {
  ll n = in_ll();
  ll m = in_ll();

  vector<set<ll>> g(n + 1);
  rep(_, m) {
    ll a, b;
    cin >> a >> b;
    g[a].insert(b);
    g[b].insert(a);
  }

  ll q = in_ll();
  rep(_, q) {
    ll x, k;
    cin >> x >> k;
    set<ll> done;
    auto dfs = [&](auto &self, ll i, ll c) {
      done.insert(i);
      if (c == 0)
        return;
      fore(ad, g[i]) { self(self, ad, c - 1); }
      return;
    };
    dfs(dfs, x, k);
    dbg(done);
    print(sum(done));
  }

  return 0;
}

Submission Info

Judge Result