結果

問題 No.2888 Mamehinata
ユーザー wai4uwai4u
提出日時 2024-09-14 01:22:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 10,294 bytes
コンパイル時間 2,787 ms
コンパイル使用メモリ 223,620 KB
実行使用メモリ 16,760 KB
最終ジャッジ日時 2024-09-14 01:22:50
合計ジャッジ時間 8,792 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 21 ms
5,376 KB
testcase_14 AC 20 ms
7,296 KB
testcase_15 AC 80 ms
9,600 KB
testcase_16 AC 96 ms
13,256 KB
testcase_17 AC 18 ms
7,524 KB
testcase_18 AC 40 ms
5,888 KB
testcase_19 AC 109 ms
13,328 KB
testcase_20 AC 84 ms
11,392 KB
testcase_21 AC 86 ms
11,008 KB
testcase_22 AC 35 ms
9,216 KB
testcase_23 AC 52 ms
11,340 KB
testcase_24 AC 94 ms
14,292 KB
testcase_25 AC 77 ms
13,952 KB
testcase_26 AC 77 ms
13,768 KB
testcase_27 AC 36 ms
11,776 KB
testcase_28 AC 15 ms
5,376 KB
testcase_29 AC 38 ms
8,064 KB
testcase_30 AC 118 ms
14,632 KB
testcase_31 AC 89 ms
13,104 KB
testcase_32 AC 54 ms
9,984 KB
testcase_33 AC 83 ms
12,320 KB
testcase_34 AC 68 ms
10,496 KB
testcase_35 AC 53 ms
9,600 KB
testcase_36 AC 127 ms
15,696 KB
testcase_37 AC 140 ms
16,016 KB
testcase_38 AC 28 ms
6,940 KB
testcase_39 AC 111 ms
13,648 KB
testcase_40 AC 138 ms
15,656 KB
testcase_41 AC 17 ms
5,632 KB
testcase_42 AC 118 ms
14,140 KB
testcase_43 AC 74 ms
14,156 KB
testcase_44 AC 79 ms
15,344 KB
testcase_45 AC 98 ms
16,760 KB
testcase_46 AC 11 ms
5,376 KB
testcase_47 AC 81 ms
15,116 KB
testcase_48 AC 72 ms
10,592 KB
testcase_49 AC 10 ms
5,376 KB
testcase_50 AC 30 ms
6,016 KB
testcase_51 AC 3 ms
5,376 KB
testcase_52 AC 2 ms
5,376 KB
testcase_53 AC 6 ms
5,376 KB
testcase_54 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <set>
using namespace std;
#include <vector>
using std::vector;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
using vvvc = vc<vvc<T>>;
template <class T>
using vvvvc = vc<vvvc<T>>;
#define VC(T, a, ...) auto a = vector<T>(__VA_ARGS__)
#define VVC(T, a, n, ...) \
  auto a = vector(n, vector<T>(__VA_ARGS__));
#define VVVC(T, a, n, m, ...) \
  auto a = vector(n, vector(m, vector<T>(__VA_ARGS__)));
#define VVVVC(T, a, n, m, l, ...) \
  auto a = \
    vector(n, vector(m, vector(l, vector<T>(__VA_ARGS__))));
#define be begin()
#define en end()
#define all(a) (a).be, (a).en
#define rbe rbegin()
#define ren rend()
#define allr(a) a.rbe, a.ren
#include <algorithm>
using std::sort;
template<class A>
void sort(A& a) { sort(all(a)); }
#include <algorithm>
using std::sort;
template<class A>
void sortr(A& a) { sort(allr(a)); }
#include <algorithm>
using std::reverse;
template<class A>
void reverse(A& a) { reverse(all(a)); }
#define eval_0(a, ...) a
#define eval_1(a, b, ...) b
#define eval_2(a, b, c, ...) c
#define eval_3(a, b, c, d, ...) d
#define eval_4(a, b, c, d, e, ...) e
#define eval_5(a, b, c, d, e, f, ...) f
#define eval_6(a, b, c, d, e, f, g, ...) g
#define iter_1(a, A) for (auto&& a : A)
#define iter_2(a, b, A) for (auto&& [a, b] : A)
#define iter_3(a, b, c, A) for (auto&& [a, b, c] : A)
#define iter_4(a, b, c, d, A) for (auto&& [a, b, c, d] : A)
#define iter_5(a, b, c, d, e, A) \
  for (auto&& [a, b, c, d, e] : A)
#define iter(...) \
  eval_6(__VA_ARGS__, iter_5, iter_4, iter_3, iter_2, iter_1)( \
    __VA_ARGS__ \
  )
#define pb push_back
#define eb emplace_back
#define emp emplace
#include <numeric>
using std::accumulate;
template<class T, class U>
T sum(const vc<U>& a) { return accumulate(all(a), T(0)); }
#define loop while (1)
using ll = long long;
#define FOR_1(i, n) for (int i = 0; i < n; i++)
#define FOR_2(i, a, b) for (ll i = a; i < b; i++)
#define FOR_3(i, a, b, c) for (ll i = a; i < b; i += c)
#define FOR(...) \
  eval_4(__VA_ARGS__, FOR_3, FOR_2, FOR_1, rep)(__VA_ARGS__)
#define FORR_1(i, n) for (int i = n; i-- > 0;)
#define FORR_2(i, l, r) for (ll i = r; i-- > l;)
#define FORR_3(i, l, r, d) for (ll i = r - 1; i >= l; i -= c)
#define FORR(...) \
  eval_4(__VA_ARGS__, FORR_3, FORR_2, FORR_1)(__VA_ARGS__)
#define rep(t) for (int __ = 0; __ < t; ++__)
template <class T, class F>
T binary_search(F f, T ok, T ng) {
  while (abs(ok - ng) > 1) {
    T x = (ok + ng) / 2;
    (f(x) ? ok : ng) = x;
  }
  return ok;
}
#include <algorithm>
using std::lower_bound;
using std::upper_bound;
template<class A, class T>
auto lb(A& a, const T& x) { return lower_bound(all(a), x); }
template<class A, class T>
int lbi(const A& a, const T& x) { return lb(a, x) - a.be; }
template<class A, class T>
auto ub(A& a, const T& x) { return upper_bound(all(a), x); }
template<class A, class T>
int ubi(const A& a, const T& x) { return ub(a, x) - a.be; }
#include <string>
using std::string;
using str = string;
template<class A>
int len(const A& a) { return a.size(); }
#include <iostream>
using std::cout;
#define yesno(y, n) \
  void y(bool f = 1) { cout << (f ? #y : #n) << '\n'; } \
  void n(bool f = 1) { y(!f); }
yesno(yes, no);
yesno(Yes, No);
yesno(YES, NO);
template<class T=int>
vc<T> iota(int n, T v=0) {
  vc<T> a(n);
  iota(all(a), v);
  return a;
}
#include <utility>
using std::pair;
using pii = pair<int, int>;
#include <utility>
using std::pair;
using pll = pair<ll, ll>;
using vii = vc<pii>;
using vll = vc<pll>;
#define mt make_tuple
#define ins insert
template <class T, class U>
bool chmax(T& a, const U& b) { return b > a ? a = b, 1 : 0; }
template <class T, class U>
bool chmin(T& a, const U& b) { return b < a ? a = b, 1 : 0; }
using dbl = double;
using ld = long double;
#include <tuple>
using std::tuple;
template <class... T>
using tup = tuple<T...>;
#include <queue>
using std::priority_queue;
template<class T>
using max_que = priority_queue<T>;
using std::greater;
template<class T>
using min_que = priority_queue<T, vc<T>, greater<T>>;

template<class T>
T pop(min_que<T>& q) { T v = q.top(); q.pop(); return v; }
template<class T>
T pop(max_que<T>& q) { T v = q.top(); q.pop(); return v; }
#include <algorithm>
using std::max_element;
using std::min_element;
template <class A>
auto max(const A& a) { return *max_element(all(a)); }
template <class A>
auto min(const A& a) { return *min_element(all(a)); }
template <class T>
T max(const set<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const set<T>& s) {
  return *s.be;
}
template <class T>
T max(const multiset<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const multiset<T>& s) {
  return *s.be;
}
#include <bits/stdc++.h>
using namespace std;
template <typename... T>
constexpr auto min(T... a) {
  using U = common_type_t<T...>;
  return std::min(initializer_list<U>{a...});
}
template <typename... T>
constexpr auto max(T... a) {
  using U = common_type_t<T...>;
  return std::max(initializer_list<U>{a...});
}
#define fi first
#define se second
#include <functional>
using std::function;
template <class F>
using fn = function<F>;
template <class A>
A fancy(const A& a, const vc<int>& p) {
  int n = len(p);
  A b(n);
  FOR(i, n) b[i] = a[p[i]];
  return b;
}
template <class A>
vc<int> argsort(const A& a) {
  auto p = iota(len(a));
  sort(all(p), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j];
  });
  return p;
}
vc<int> argperm(const vc<int>& p) {
  int n = len(p);
  vc<int> a(n);
  FOR(i, n) a[p[i]] = i;
  return a;
}
template <class A>
vc<int> rankify(const A& a) {
  return argperm(argsort(a));
}
/* deprecated
*/
#include <queue>
using std::queue;
template<class T>
T pop(queue<T>& q) {
  T x = q.front();
  q.pop();
  return x;
}

#include <queue>
using std::deque;
template <class T>
T pop_front(deque<T>& q) {
  T x = q.front();
  q.pop_front();
  return x;
}
template <class T>
T pop_back(deque<T>& q) {
  T x = q.back();
  q.pop_back();
  return x;
}
template <class T>
T pop(vc<T>& a) {
  T x = a.back();
  a.pop_back();
  return x;
}
char pop(str& a) {
  char x = a.back();
  a.pop_back();
  return x;
}
class range {
  ll i, b, d;
public:
  range(ll a, ll b, ll d): i(a), b(b), d(d) {}
  range(ll a, ll b): range(a, b, a < b ? 1 : -1) {}
  range(int n): range(0, n) {}
  range& begin() { return *this; }
  range& end() { return *this; }
  range& operator++() {
    i += d;
    return *this;
  }
  bool operator!=(const range&) const {
    return d > 0 && i < b || d < 0 && i > b;
  }
  ll operator*() const { return i; }
};
template <class T>
int signum(T x) {
  return x > 0 ? 1 : x < 0 ? -1 : 0;
}
template <class T, class U>
auto divmod(T n, U k) -> pair<T, T> {
  T q = n / k;
  T r = n - q * k;
  if (signum(r) * signum(k) < 0) r += k, q--;
  return {q, r};
}
#include <random>
using std::mt19937_64;
using std::random_device;
mt19937_64 mrand(random_device{}());
int rng(int x) { return mrand() % x; }
constexpr double PI = 3.14159265358979323846;
#include <iostream>
using namespace std;
void fastio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
#include <iostream>
#include <iomanip>
using namespace std;
void precise_float() { cout << setprecision(18); }
template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
  return i >> p.fi >> p.se;
}
#include <tuple>
#include <iostream>
using namespace std;
template <int k = 0, class T>
void scan_tup(istream& i, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    i >> get<k>(x);
    scan_tup<k + 1>(i, x);
  }
}
template <class... T>
istream& operator>>(istream& i, tuple<T...>& x) {
  scan_tup(i, x);
  return i;
}
template <class I, class T>
I& operator>>(I& i, vc<T>& a) {
  iter(x, a) i >> x;
  return i;
}
#include <iostream>
using namespace std;
template <typename... T>
void scan(T&... a) { (cin >> ... >> a); }
#define VEC(T, a, n) VC(T, a, n); cin >> a;
#define V(T, a, n) VC(T, a, n); cin >> a;
#define VV(T, a, n, m) VVC(T, a, n, m); cin >> a;
#define VVV(T, a, n, m, l) VVC(T, a, n, m, l); cin >> a;
#define INT(...) int __VA_ARGS__; scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; scan(__VA_ARGS__)
#define DBL(...) dbl __VA_ARGS__; scan(__VA_ARGS__)
#define STR(...) str __VA_ARGS__; scan(__VA_ARGS__)
#define VI(a, n) V(int, a, n)
#define VL(a, n) V(ll, a, n)
#define VII(a, n) V(pii, a, n)
#define VLL(a, n) V(pll, a, n)
#define VSTR(a, n) V(str, a, n)
template <class T, size_t n>
ostream& operator<<(ostream& os, const array<T, n>& a) {
  FOR(i, n) {
    if (i) os << ' ';
    os << a[i];
  }
  return os;
}
template <class T, size_t n>
ostream& operator<<(ostream& os, array<array<T, n>, n> a) {
  FOR(i, n) os << a[i] << '\n';
  return os;
}
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
  return o << p.fi << ' ' << p.se;
}
#include <bits/stdc++.h>
using namespace std;
template <int k = 0, class T>
void out_tup(ostream& o, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    if constexpr (k > 0) o << ' ';
    o << get<k>(x);
    out_tup<k + 1>(o, x);
  }
}
template <class... T>
ostream& operator<<(ostream& o, tuple<T...>& x) {
  out_tup(o, x);
  return o;
}
template <class O, class T>
O& operator<<(O& o, vc<T> a) {
  FOR(i, len(a)) {
    if (i) o << ' ';
    o << a[i];
  }
  return o;
}
template <class O, class T>
O& operator<<(O& o, vvc<T> a) {
  iter(x, a) o << x << '\n';
  return o;
}
#include <iostream>
using namespace std;
template <class T, class... U>
void print(T a, U... b) {
  cout << a;
  ((cout << ' ' << b), ...);
  cout << '\n';
}
vc<int> bfs(const vvc<int>& g, int s) {
  vc<int> l(len(g), -1);
  l[s] = 0;
  vc<int> q{s};
  int i = 0;
  while (i < len(q)) {
    int u = q[i++];
    iter(v, g[u]) {
      if (l[v] == -1) l[v] = l[u] + 1, q.pb(v);
    }
  }
  return l;
}
int main() {
  fastio();
  int n, m;
  cin >> n >> m;
  vvc<int> g(n);
  rep(m) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].pb(v);
    g[v].pb(u);
  }
  if (g[0].empty()) {
    rep(n) print(0);
    return 0;
  }
  auto l = bfs(g, 0);
  vc<int> s(n + 1);
  iter(l, l) if (l != -1) s[l]++;
  FOR(i, n - 1) { s[i + 2] += s[i]; }
  FOR(i, 1, n + 1) { print(s[i]); }
}
0