結果

問題 No.2888 Mamehinata
ユーザー tonegawatonegawa
提出日時 2024-09-14 12:15:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 8,643 bytes
コンパイル時間 1,990 ms
コンパイル使用メモリ 153,916 KB
実行使用メモリ 24,036 KB
最終ジャッジ日時 2024-09-14 12:15:23
合計ジャッジ時間 8,153 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 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 5 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 28 ms
10,088 KB
testcase_14 AC 17 ms
6,760 KB
testcase_15 AC 65 ms
17,764 KB
testcase_16 AC 97 ms
17,772 KB
testcase_17 AC 15 ms
5,608 KB
testcase_18 AC 51 ms
15,592 KB
testcase_19 AC 107 ms
20,072 KB
testcase_20 AC 93 ms
17,640 KB
testcase_21 AC 91 ms
17,896 KB
testcase_22 AC 27 ms
8,424 KB
testcase_23 AC 39 ms
10,984 KB
testcase_24 AC 119 ms
17,256 KB
testcase_25 AC 55 ms
15,972 KB
testcase_26 AC 64 ms
15,084 KB
testcase_27 AC 32 ms
9,580 KB
testcase_28 AC 17 ms
5,740 KB
testcase_29 AC 44 ms
9,956 KB
testcase_30 AC 122 ms
19,556 KB
testcase_31 AC 97 ms
16,816 KB
testcase_32 AC 64 ms
12,776 KB
testcase_33 AC 88 ms
15,852 KB
testcase_34 AC 69 ms
13,928 KB
testcase_35 AC 68 ms
12,520 KB
testcase_36 AC 133 ms
21,092 KB
testcase_37 AC 134 ms
21,608 KB
testcase_38 AC 30 ms
8,556 KB
testcase_39 AC 90 ms
18,156 KB
testcase_40 AC 117 ms
21,352 KB
testcase_41 AC 19 ms
6,508 KB
testcase_42 AC 96 ms
18,664 KB
testcase_43 AC 92 ms
19,944 KB
testcase_44 AC 103 ms
21,988 KB
testcase_45 AC 117 ms
24,036 KB
testcase_46 AC 15 ms
5,988 KB
testcase_47 AC 99 ms
21,356 KB
testcase_48 AC 82 ms
21,864 KB
testcase_49 AC 15 ms
7,144 KB
testcase_50 AC 49 ms
16,100 KB
testcase_51 AC 4 ms
5,376 KB
testcase_52 AC 2 ms
5,376 KB
testcase_53 AC 8 ms
5,376 KB
testcase_54 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}






template <class E>
struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    csr() {}
    explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
    ~csr() {}

    int N() const {
        return start.size() - 1;
    }

    int deg(int i) const {
        return start[i + 1] - start[i];
    }

    int begin(int i) const {
        return start[i];
    }

    int end(int i) const {
        return start[i + 1];
    }

    E& operator [] (int i) { return elist[i]; }
};


// O((V + E)logV)
// 辺の重みが非負(負の閉路がなければ一応動く)
template<typename edge, typename W = typename edge::W>
struct dijkstra {
  private:
    int _s;
    csr<edge> &G;
  
  public:
    static constexpr W inf = std::numeric_limits<W>::max() / 2;
    dijkstra() {}
    dijkstra(csr<edge> &G) : G(G) {}
    std::vector<W> dist;
    std::vector<int> par;

    // targetを指定した場合targetに到達した時点で打ち切る
    void build(int s, int target = -1) {
        _s = s;
        using P = std::pair<W, int>;
        int N = G.N();
        if (dist.empty()) {
            dist.resize(N, inf);
            par.resize(N, -1);
        } else {
            std::fill(dist.begin(), dist.end(), inf);
            std::fill(par.begin(), par.end(), -1);
        }
        std::priority_queue<P, std::vector<P>, std::greater<P>> que;
        dist[s] = 0;
        que.push({0, s});
        while (!que.empty()) {
            auto [w, v] = que.top();
            if (v == target) break;
            que.pop();
            if (dist[v] < w) continue;
            for (int i = G.begin(v); i < G.end(v); i++) {
                int to = G.elist[i];
                W d = dist[v] + G.elist[i].weight();
                if (dist[to] > d) {
                    dist[to] = d;
                    par[to] = v;
                    que.push(P{d, to});
                }
            }
        }
    }
    
    // 到達不可能な場合空
    std::vector<int> path(int t) {
        assert(!dist.empty());
        if (par[t] == -1) return {};
        std::vector<int> res{t};
        while (t != _s) {
            t = par[t];
            res.push_back(t);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    W operator [](int v) const { return dist[v]; }
};




template<typename _W>
struct edge_base {
    using W = _W;
    int t;
    edge_base() {}
    edge_base(int _t) : t(_t) {}

    virtual int from() const {
        assert(false);
    }

    int to() const {
        return t;
    }
    
    virtual W weight() const {
        assert(false);
    }

    operator int() const {
        return t;
    }
};

struct simple_edge : edge_base<int> {
    simple_edge() {}
    simple_edge(int _t) : edge_base<int>(_t) {}
    int weight() const override {
        return 1;
    }
};

template<typename _W>
struct weighted_edge : edge_base<_W> {
    using W = _W;
    W w;
    weighted_edge() {}
    weighted_edge(int _t, _W _w) : edge_base<_W>(_t), w(_w) {}
    W weight() const override {
        return w;
    }
};




int main() {
    io_init();
    int N, M;
    std::cin >> N >> M;
    using edge = simple_edge;
    std::vector<std::pair<int, simple_edge>> E;
    for (int i = 0; i < M; i++) {
        int a, b;
        std::cin >> a >> b;
        a--, b--;
        E.push_back({a, {b}});
        E.push_back({b, {a}});
    }
    csr<edge> G(N, E);

    if (G.begin(0) == G.end(0)) {
        for (int i = 0; i < N; i++) {
            std::cout << 0 << '\n';
        }
        return 0;
    }
    dijkstra<edge> D(G);
    D.build(0);
    auto d = D.dist;
    sort(allof(d));

    int j = 0, e = 0, o = 0;
    for (int t = 1; t <= N; t++) {
        while (j < N && d[j] <= t) {
            if (d[j] % 2 == 0) e++;
            else o++;
            j++;
        }
        if (t & 1) {
            std::cout << o << '\n';
        } else {
            std::cout << e << '\n';
        }
    }
}
0