結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 22:11:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 112 ms / 4,000 ms |
コード長 | 1,480 bytes |
コンパイル時間 | 1,612 ms |
コンパイル使用メモリ | 178,500 KB |
実行使用メモリ | 10,004 KB |
最終ジャッジ日時 | 2024-06-12 19:06:08 |
合計ジャッジ時間 | 5,572 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) #define unless(p) if(!(p)) #define until(p) while(!(p)) using ll = std::int64_t; using P = std::tuple<int,int>; const int INF = 1001001001; int N, M; std::vector<int> G[100100]; int Q, A; int dist[100100]; std::queue<P> que; void dijkstra(int s){ std::fill(dist + 1, dist + 1 + N, INF); dist[s] = 0; que.emplace(0, s); until(que.empty()){ int d, v; std::tie(d, v) = que.front(); que.pop(); if(d > dist[v]){ continue; } for(int w : G[v]){ int di = dist[v] + 1; if(di < dist[w]){ dist[w] = di; que.emplace(di, w); } } } } int f(int n){ if(n <= 1){ return 0; } return 32 - __builtin_clz(n - 1); } int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> N >> M; for(int i=0;i<M;++i){ int p, q; std::cin >> p >> q; G[p].emplace_back(q); G[q].emplace_back(p); } std::cin >> Q; for(int i=0;i<Q;++i){ std::cin >> A; dijkstra(A); int c = 0, d = 0; for(int j=1;j<=N;++j){ if(j != A && dist[j] < INF){ c += 1; d = std::max(d, f(dist[j])); } } std::cout << c << " " << d << std::endl; } }