結果
問題 | No.812 Change of Class |
ユーザー |
|
提出日時 | 2020-11-16 15:17:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,294 ms / 4,000 ms |
コード長 | 1,291 bytes |
コンパイル時間 | 2,554 ms |
コンパイル使用メモリ | 206,400 KB |
最終ジャッジ日時 | 2025-01-16 01:10:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T, T INF>vector<T> dijkstra(const vector<vector<pair<int, int>>> &g, int st = 0) {const int n = g.size();vector<T> dis(n, INF); {set<pair<T, int>> bag;bag.emplace(dis[st] = 0, st);while (bag.size()) {auto [d, u] = *bag.begin();bag.erase(bag.begin());if (d != dis[u]) continue;for (auto [w, v] : g[u]) {if (d + w < dis[v]) {bag.emplace(dis[v] = d + w, v);}}}}return dis;}int main() {ios::sync_with_stdio(false);int N, M; {cin >> N >> M;}vector<vector<pair<int, int>>> G(N); {for (int i = 0; i < M; ++i) {int U, V; {cin >> U >> V;--U, --V;}G[U].emplace_back(1, V);G[V].emplace_back(1, U);}}int Q; { cin >> Q; }while (Q--) {int A; {cin >> A;--A;}int cnt = 0;int maxd = 0; {const int INF = 0x3f3f3f3f;auto dis = dijkstra<int, INF>(G, A);for (int u = 0; u < N; ++u) if (u != A) {if (dis[u] == INF) continue;++cnt;maxd = max(maxd, dis[u]);}}auto f = [](int d) { return d ? ceil(log2(d)) : 0; };cout << cnt << ' ' << f(maxd) << endl;}}