結果

問題 No.2888 Mamehinata
ユーザー umimelumimel
提出日時 2024-09-13 22:45:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 11,639 bytes
コンパイル時間 1,956 ms
コンパイル使用メモリ 182,444 KB
実行使用メモリ 22,884 KB
最終ジャッジ日時 2024-09-13 22:45:22
合計ジャッジ時間 8,370 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 30 ms
9,700 KB
testcase_14 AC 21 ms
7,992 KB
testcase_15 AC 111 ms
17,524 KB
testcase_16 AC 124 ms
19,308 KB
testcase_17 AC 21 ms
7,980 KB
testcase_18 AC 60 ms
14,788 KB
testcase_19 AC 140 ms
20,768 KB
testcase_20 AC 144 ms
18,588 KB
testcase_21 AC 112 ms
18,728 KB
testcase_22 AC 38 ms
10,572 KB
testcase_23 AC 58 ms
13,488 KB
testcase_24 AC 116 ms
19,748 KB
testcase_25 AC 86 ms
17,896 KB
testcase_26 AC 83 ms
17,256 KB
testcase_27 AC 37 ms
12,724 KB
testcase_28 AC 17 ms
6,940 KB
testcase_29 AC 48 ms
10,376 KB
testcase_30 AC 143 ms
20,992 KB
testcase_31 AC 118 ms
18,068 KB
testcase_32 AC 68 ms
13,580 KB
testcase_33 AC 101 ms
18,300 KB
testcase_34 AC 86 ms
14,904 KB
testcase_35 AC 69 ms
13,072 KB
testcase_36 AC 151 ms
22,164 KB
testcase_37 AC 161 ms
22,884 KB
testcase_38 AC 35 ms
9,104 KB
testcase_39 AC 144 ms
20,228 KB
testcase_40 AC 172 ms
22,332 KB
testcase_41 AC 21 ms
6,948 KB
testcase_42 AC 133 ms
19,692 KB
testcase_43 AC 81 ms
18,616 KB
testcase_44 AC 87 ms
20,564 KB
testcase_45 AC 102 ms
21,696 KB
testcase_46 AC 12 ms
6,944 KB
testcase_47 AC 88 ms
19,640 KB
testcase_48 AC 90 ms
18,200 KB
testcase_49 AC 14 ms
6,940 KB
testcase_50 AC 44 ms
15,524 KB
testcase_51 AC 4 ms
6,944 KB
testcase_52 AC 2 ms
6,940 KB
testcase_53 AC 7 ms
6,940 KB
testcase_54 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In static member function 'static std::vector<_Tp> shortest_path::dijkstra(graph<T>&, int)':
main.cpp:213:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  213 |             auto [d, v] = que.top();
      |                  ^
main.cpp: In static member function 'static std::vector<std::vector<std::pair<int, T> > > shortest_path::pered(graph<T>&, int)':
main.cpp:284:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  284 |             auto [d, v, s] = que.top();
      |                  ^

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 2;


template<typename T> 
struct edge{
    int from;
    int to;
    T cost;
    int id;

    edge(){}
    edge(int to, T cost=1) : from(-1), to(to), cost(cost){}
    edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}
    edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}

    void reverse(){swap(from, to);}
};

template<typename T>
struct edges : std::vector<edge<T>>{
    void sort(){
        std::sort(
            (*this).begin(),
            (*this).end(), 
            [](const edge<T>& a, const edge<T>& b){
                return a.cost < b.cost;
            }
        );
    }
};

template<typename T = bool>
struct graph : std::vector<edges<T>>{
private:
    int n = 0;
    int m = 0;
    edges<T> es;
    bool dir;

public:
    graph(int n, bool dir) : n(n), dir(dir){
        (*this).resize(n);
    }

    void add_edge(int from, int to, T cost=1){
        if(dir){
            es.push_back(edge<T>(from, to, cost, m));
            (*this)[from].push_back(edge<T>(from, to, cost, m++));
        }else{
            if(from > to) swap(from, to);
            es.push_back(edge<T>(from, to, cost, m));
            (*this)[from].push_back(edge<T>(from, to, cost, m));
            (*this)[to].push_back(edge<T>(to, from, cost, m++));
        }
    }

    int get_vnum(){
        return n;
    }

    int get_enum(){
        return m;
    }

    bool get_dir(){
        return dir;
    }

    edge<T> get_edge(int i){
        return es[i];
    }

    edges<T> get_edge_set(){
        return es;
    }
};

template<typename T>
struct redge{
    int from, to;
    T cap, cost;
    int rev;
    
    redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
    redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};

template<typename T> using Edges = vector<edge<T>>;
template<typename T> using weighted_graph = vector<Edges<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;


class shortest_path{
public:
    template<typename T>
    static vector<T> bfs(graph<T> &G, int s){
        int n = G.get_vnum();
        vector<T> dist(n, -1);

        dist[s] = 0;
        queue<int> que;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for(auto e : G[v]) if(dist[e.to]==-1){
                dist[e.to] = dist[v] + 1;
                que.push(e.to);
            }
        }

        return dist;
    }

    template<typename T>
    static vector<T> binary_bfs(graph<T> &G, int s){
        int n = G.get_vnum();
        vector<T> dist(n, -1);

        dist[s] = 0;
        deque<int> deq;
        deq.push_front(s);
        while(!deq.empty()){
            int v = deq.front();
            deq.pop_front();
            for(auto e : G[v]) if(dist[e.to]==-1){
                dist[e.to] = dist[v] + e.cost;
                if(e.cost) deq.push_back(e.to);
                else deq.push_front(e.to);
            }
        }

        return dist;
    }

    template<typename T>
    static vector<T> constant_bfs(graph<T> &G, int s, T W){
        int n = G.get_vnum();
        vector<T> dist(n, -1);
        vector<vector<int>> cand(n*W+1);

        dist[s] = 0;
        cand[0].push_back(s);
        for(int d=0; d<=n*W; d++) for(int v : cand[d]){
            if(dist[v]!=-1) continue;
            for(auto e : G[v]) if(dist[v] + dist[e.to] < dist[e.ot]){
                dist[e.to] = dist[v] + e.cost;
                cand[dist[e.to]].push_back(e.to);
            }
        }

        return dist;
    }

    template<typename T>
    static vector<T> complement_bfs(graph<T> &G, int s){
        int n = G.get_vnum();
        map<pair<int, int>, bool> mp;
        for(int v=0; v<n; v++) for(auto e : G[v]) mp[{v, e.to}] = true;

        vector<T> dist(n, -1);
        vector<int> unvisited;
        for(int v=0; v<n; v++) if(v != s) unvisited.push_back(v);
        queue<int> visited;
        visited.push(s);
        dist[s] = 0;

        while(!visited.empty()){
            int v = visited.front();
            visited.pop();

            vector<int> nxt;
            for(int to : unvisited){
                if(!mp[{v, to}]){
                    visited.push(to);
                    dist[to] = dist[v]+1;
                }else{
                    nxt.pb(to);
                }
            }

            unvisited = nxt;
        }

        return dist;
    }

    template<typename T>
    static vector<T> dijkstra(graph<T> &G, int s){
        int n = G.get_vnum();
        const T TINF = numeric_limits<T>::max()/2;
        vector<T> dist(n, TINF);

        dist[s] = 0;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> que;
        que.push({0, s});
        while(!que.empty()){
            auto [d, v] = que.top();
            que.pop();
            if(dist[v] < d) continue;

            for(auto e : G[v]){
                if(dist[v] + e.cost < dist[e.to]){
                    dist[e.to] = dist[v] + e.cost;
                    que.push({dist[e.to], e.to});
                }
            }
        }

        for(int v=0; v<n; v++) if(dist[v]==TINF) dist[v] = -1;

        return dist;
    }
    
    template<typename T>
    static vector<T> bellmanford(graph<T> &G, int s){
        int n = G.get_vnum();
        bool dir = G.get_dir();
        const T TINF = numeric_limits<T>::max()/2;
        edges<T> es = G.get_edge_set();
        vector<T> dist(n, TINF);
        vector<bool> flag(n, false);

        dist[s] = 0;
        for(int i=0; i<n; i++) for(auto e : es){
            if(dist[e.from]!=TINF && dist[e.from]+e.cost<dist[e.to]) dist[e.to] = dist[e.from] + e.cost;
            if(!dir && dist[e.to]!=TINF && dist[e.to]+e.cost<dist[e.from]) dist[e.from] = dist[e.to] + e.cost;
        }

        for(int i=0; i<n; i++) for(auto e : es){
            if(dist[e.from]!=TINF && dist[e.from]+e.cost<dist[e.to]) dist[e.to] = dist[e.from] + e.cost, flag[e.to]=true;
            if(!dir && dist[e.to]!=TINF && dist[e.to]+e.cost<dist[e.from]) dist[e.from] = dist[e.to] + e.cost, flag[e.from]=true;
        }

        for(int i=0; i<n; i++) for(auto e : es){
            flag[e.to] = flag[e.to] | flag[e.from];
            if(!dir) flag[e.from] = flag[e.from] | flag[e.to];
        }
        for(int v=0; v<n; v++) if(flag[v]) dist[v] = -TINF;

        return dist;
    }

    template<typename T>
    static vector<vector<T>> warshall_floyd(graph<T> &G){
        int n = G.get_vnum();
        const T TINF = numeric_limits<T>::max()/2;
        vector<vector<T>> dist(n, vector<T>(n, TINF));
        
        for(int v=0; v<n; v++) dist[v][v] = 0;
        for(int v=0; v<n; v++) for(auto e : G[v]) dist[v][e.to] = min(dist[v][e.to], e.cost);
        for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(dist[i][k] < TINF && dist[k][j] < TINF) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        return dist;
    }

    template<typename T>
    static vector<vector<pair<int, T>>> pered(graph<T> &G, int k){
        int n = G.get_vnum();
        const T TINF = numeric_limits<T>::max()/2;
        priority_queue<tuple<T, int, int>, vector<tuple<T, int, int>>, greater<>> que;
        vector<vector<pair<int, T>>> neibors(n);
        vector<unordered_map<int, T>> mp(n);
        for(int v=0; v<n; v++){
            que.push({0, v, v});
            mp[v][v] = 0;
        }
        while(!que.empty()){
            auto [d, v, s] = que.top();
            que.pop();
            if((int)neibors[v].size()==k) continue;
            if(mp[v].find(s)!=mp[v].end()) if(mp[v][s] < d) continue;
            neibors[v].push_back({s, d});

            for(auto e : G[v]){
                if((int)neibors[e.to].size()==k) continue;
                if(mp[e.to].find(s)==mp[e.to].end()) mp[e.to][s] = TINF;
                if(d + e.cost < mp[e.to][s]){
                    mp[e.to][s] = d + e.cost;
                    que.push({d+e.cost, e.to, s});
                }
            }
        }

        return neibors;
    }

    // template<typename T>
    // static T malick_mittal_gupta(graph<T> &G, int s, int t){
    //     // declear variable
    //     const T TINF = numeric_limits<T>::max()/2;
    //     dijkstra<T> dijk_s(G, s), dijk_t(G, t);
    //     int n = G.get_vnum();
    //     int m = G.get_enum();
    //     vector<T> dist_s = dijk_s.get_dist();
    //     vector<T> dist_t = dijk_t.get_dist();
    //     vector<int> path = dijk_s.get_vpath(t);
    //     int p = (int)path.size();
    //     path.push_back(n); // sentinel
    //     vector<vector<int>> ch(n);
    //     for(int v=0; v<n; v++) if(v != s) ch[dijk_s.get_vpar(v)].push_back(v);
    //     vector<int> label(n, -1);


    //     function<void(int, int)> labeling = [&](int v, int l){
    //         label[v] = l;
    //         for(int to : ch[v]) dfs(to, l);
    //     };
        
    //     for(int i=0; i<p; i++){
    //         label[path[i]] = i;
    //         for(int to : ch[path[i]]) if(to != path[i+1]){
    //             dfs(to, path[i], i);
    //         }
    //     }

    //     vector<vector<int>> sevt(p), eevt(p);
    //     for(int v=0; v<n; v++) for(auto e : G[v]) if(dijk_s.get_epar(e.to).id != e.id && label[v] < label[e.to]){
    //         sevt[label[v]].push_back(e.id);
    //         tevt[label[v]].push_back(e.id);
    //     }
        

    //     T ans = TINF;
    //     for(int i=1; i<p; i++){
    //         int u = path[i-1], v = path[i], e_id = dijk_s.get_epar(v);
        
    //         // start event with label = i-1
    //         for(int id : sevt[i-1]){
    //             auto e = G.get_edge(id);
    //             int x = e.from, y = e.to;
    //             if(label[x] > label[y]) swap(x, y);
    //             eset.insert({dist_s[x]+e.cost+dist_t[y], id});
    //         }

    //         // calc ans
    //         if(!eset.empty()) ans = min(ans, (*eset.begin()).first);

    //         // end event with label = i
    //         for(int id : evt[i]){
    //             auto e = G.get_edge(id);
    //             int x = e.from, y = e.to;
    //             if(label[x] > label[y]) swap(x, y);
    //             eset.erase({dist_s[x]+e.cost+dist_t[y], id});
    //         }
    //     }

    //     return ans;
    // }

    template<typename T>
    static vector<T> yen(graph<T> &G, int s, int t, int k){
        
    }
};


void solve(){
    int n, m; cin >> n >> m;
    graph<int> G(n, false);
    for(int i=0; i<m; i++){
        int u, v; cin >> u >> v;
        u--; v--;
        G.add_edge(u, v);
    }

    if((int)G[0].size()==0){
        for(int i=1; i<=n; i++) cout << 0 << '\n';
        return;
    }

    vector<int> dist = shortest_path::bfs<int>(G, 0);
    vector<int> cnt(n+1, 0);
    for(int v=0; v<n; v++) if(dist[v]!=-1) cnt[dist[v]]++;
    vector<int> sum(2, 0);
    sum[0] = cnt[0];
    for(int i=1; i<=n; i++){
        sum[i%2]+=cnt[i];
        cout << sum[i%2] << '\n'; 
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    //cin >> T;
    while(T--) solve();
}
0