結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 22:55:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 530 ms / 4,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 1,924 ms |
コンパイル使用メモリ | 182,236 KB |
実行使用メモリ | 15,372 KB |
最終ジャッジ日時 | 2024-06-12 19:49:45 |
合計ジャッジ時間 | 13,973 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include "bits/stdc++.h"#define in std::cin#define out std::cout#define rep(i,N) for(LL i=0;i<N;++i)typedef long long int LL;typedef std::pair<LL, LL> P;struct edge { LL to, cost; };const LL inf = 1123456789;std::vector<LL>dist;std::vector<std::vector<edge>>G;void dijkstra(LL s){std::priority_queue<P, std::vector<P>, std::greater<P>>que;std::fill(dist.begin(), dist.end(), inf);dist[s] = 0;que.push(P(0, s));while (!que.empty()){P p = que.top(); que.pop();LL v = p.second;if (dist[v] < p.first) continue;rep(i, G[v].size()){edge e = G[v][i];if (dist[e.to] > dist[v] + e.cost){dist[e.to] = dist[v] + e.cost;que.push(P(dist[e.to], e.to));}}}}int main(){LL N, M, Q;in >> N >> M;std::vector<LL>p(M), q(M);rep(i, M) in >> p[i] >> q[i];in >> Q;std::vector<LL>A(Q);rep(i, Q) in >> A[i];G.resize(N + 1);rep(i, M){G[p[i]].push_back({ q[i],1 });G[q[i]].push_back({ p[i],1 });}rep(i, Q){dist.clear();dist.resize(N + 1);dijkstra(A[i]);LL ans1 = 0, ans2 = 0;for (LL j = 1; j <= N; ++j){if (A[i] == j) continue;if (dist[j] < inf){++ans1;if (dist[j] > 1){LL temp = dist[j] - 1, res = 0;while (temp > 0){temp /= 2;++res;}ans2 = std::max(ans2, res);}}}out << ans1 << " " << ans2 << std::endl;}}