結果

問題 No.812 Change of Class
ユーザー mu6
提出日時 2019-04-12 23:10:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 159 ms / 4,000 ms
コード長 1,537 bytes
コンパイル時間 2,134 ms
コンパイル使用メモリ 167,852 KB
実行使用メモリ 11,996 KB
最終ジャッジ日時 2024-06-12 19:49:56
合計ジャッジ時間 6,952 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 端点を間違えないように気をつけること!
#define FOR(i, m, n) for (ll i = (ll)(m); i <= (ll)(n); i++)
#define RFOR(i, m, n) for (ll i = (ll)(m); i >= (ll)(n); i--)
// 割り算をするときは自作関数syou,amariを使うこと!
// 入力は変数を宣言した直後に入れること!

int main()
{
    ll N, M;
    cin >> N >> M;
    ll p[M + 1], q[M + 1];
    vector<ll> yuujin[N + 1];
    FOR(i, 1, M)
    {
        cin >> p[i] >> q[i];
        yuujin[p[i]].push_back(q[i]);
        yuujin[q[i]].push_back(p[i]);
    }
    ll Q;
    cin >> Q;
    ll A[Q + 1];
    FOR(i, 1, Q)
    {
        cin >> A[i];
        ll friends = -1;
        ll mini[N + 1];
        FOR(i, 0, N)
        {
            mini[i] = -1;
        }
        queue<ll> que;
        que.push(A[i]);
        mini[A[i]] = 0;
        while (!que.empty())
        {
            ll p = que.front();
            que.pop();
            friends++;
            FOR(j, 0, yuujin[p].size() - 1)
            {
                if (mini[yuujin[p][j]] == -1)
                {
                    mini[yuujin[p][j]] = mini[p] + 1;
                    que.push(yuujin[p][j]);
                }
            }
        }
        ll maxd = 0;
        FOR(j, 1, N)
        {
            maxd = max(maxd, mini[j]);
        }
        if (maxd != 0)
            cout << friends << " " << (ll)ceil(log(maxd) / log(2.0)) << endl;
        else
            cout << friends << " " << 0 << endl;
    }
}
0