結果
問題 | No.2888 Mamehinata |
ユーザー | umimel |
提出日時 | 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(); | ^
ソースコード
#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(); }