結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2020-01-15 13:49:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,291 bytes |
コンパイル時間 | 2,021 ms |
コンパイル使用メモリ | 180,888 KB |
実行使用メモリ | 20,400 KB |
最終ジャッジ日時 | 2024-06-12 21:43:14 |
合計ジャッジ時間 | 21,005 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 48 |
ソースコード
#include<bits/stdc++.h> using namespace std; #ifdef LOCAL_DEBUG #include "LOCAL_DEBUG.hpp" #endif #define int long long const int INF = 1LL << 60; struct edge{ int to,cost; }; vector<int> dikstra(int s,vector<vector<edge>> G){ typedef pair<int, int> P; const int INF = 1LL << 60; priority_queue<P,vector<P>,greater<P>> que; vector<int> d(G.size(),INF); //sからの最短距離 d[s] = 0; que.push({0,s}); //{最短距離,頂点} while( !que.empty() ){ P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(auto e : G[v]){ if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push( {d[e.to],e.to} ); } } } return d; } signed main(){ int n, m; cin >> n >> m; vector<vector<edge>> G(n); for(int i = 0; i < m; i++){ int s, t; cin >> s >> t; s--, t--; G[s].push_back({t, 1}); G[t].push_back({s, 1}); } int q; cin >> q; for(int i = 0; i < q; i++){ int s; cin >> s; s--; auto dp = dikstra(s, G); int friends = 0, date = 0; for(int i = 0; i < n; i++){ if(i != s && dp[i] != INF){ friends++; date = max(date, dp[i]); } } if(date == 1) date--; cout << friends << " " << (date+1)/2 << endl; } return 0; }