結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 21:56:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 4,000 ms |
コード長 | 1,262 bytes |
コンパイル時間 | 1,614 ms |
コンパイル使用メモリ | 177,488 KB |
実行使用メモリ | 9,792 KB |
最終ジャッジ日時 | 2024-06-12 07:13:46 |
合計ジャッジ時間 | 5,971 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h>using namespace std;using lint = long long;template<class T = int> using V = vector<T>;template<class T = int> using VV = V< V<T> >;struct UnionFind {const int n;V<> t; // root ? -sz : parUnionFind(int n) : n(n), t(n, -1) {}int find(int v) { return t[v] < 0 ? v : t[v] = find(t[v]); }void unite(int u, int v) {if ((u = find(u)) == (v = find(v))) return;if (-t[u] < -t[v]) swap(u, v);t[u] += t[v];t[v] = u;}bool same(int u, int v) { return find(u) == find(v); }int size(int v) { return -t[find(v)]; }};int main() {cin.tie(nullptr); ios::sync_with_stdio(false);int n, m; cin >> n >> m;VV<> g(n);UnionFind uf(n);while (m--) {int u, v; cin >> u >> v, --u, --v;g[u].push_back(v);g[v].push_back(u);uf.unite(u, v);}int q; cin >> q;while (q--) {int a; cin >> a, --a;V<> d(n, -1);queue<int> que;d[a] = 0;que.emplace(a);while (!que.empty()) {int v = que.front(); que.pop();for (int w : g[v]) if (d[w] == -1) {d[w] = d[v] + 1;que.emplace(w);}}int mx = *max_element(begin(d), end(d));cout << uf.size(a) - 1 << ' ' << !!(uf.size(a) - 1) * __lg(2 * mx - 1) << '\n';}}