結果
| 問題 | No.2888 Mamehinata |
| ユーザー |
 tonegawa
|
| 提出日時 | 2024-09-14 12:15:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 123 ms / 2,000 ms |
| コード長 | 8,643 bytes |
| コンパイル時間 | 1,923 ms |
| コンパイル使用メモリ | 148,116 KB |
| 最終ジャッジ日時 | 2025-02-24 08:28:56 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 52 |
ソースコード
#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';}}}