結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-12 22:10:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 218 ms / 4,000 ms |
コード長 | 2,814 bytes |
コンパイル時間 | 1,374 ms |
コンパイル使用メモリ | 122,812 KB |
実行使用メモリ | 12,756 KB |
最終ジャッジ日時 | 2024-06-12 18:35:47 |
合計ジャッジ時間 | 7,422 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
/* ---------- STL Libraries ---------- */// IO library#include <cstdio>#include <fstream>#include <iomanip>#include <ios>#include <iostream>// algorithm library#include <algorithm>#include <cmath>#include <numeric>#include <random>#include <cstring>// container library#include <array>#include <bitset>#include <deque>#include <map>#include <unordered_map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>#include <stack>/* ---------- Namespace ---------- */using namespace std;/* ---------- Type ---------- */using ll = long long;#define int ll#define P pair<ll, ll>/* ---------- Constants */const double PI = 3.141592653589793238462643383279;const ll MOD = 1e9 + 7;const int INF = 1LL << 55;class UnionFind {public:vector<int> par, rank;vector<int> forest_size;int forest_cnt;int N;UnionFind(int n) : forest_cnt(n), N(N) {par = vector<int>(n);iota(par.begin(), par.end(), 0);rank = vector<int>(n, 0);forest_size.resize(n, 1);}int root(int x) {if (par[x] == x) {return x;} else {return par[x] = root(par[x]);}}void unite(int x, int y) {x = root(x);y = root(y);if (x == y) return;int fsz = forest_size[x] + forest_size[y];if (rank[x] < rank[y]) {par[x] = y;forest_size[y] = fsz;} else {par[y] = x;forest_size[x] = fsz;if (rank[x] == rank[y]) rank[x]++;}forest_cnt--;}bool same(int x, int y) {return root(x) == root(y);}int get_forest_size(int x) {return forest_size[root(x)];}};signed main() {int N, M;cin >> N >> M;vector<int> table[N];UnionFind uf = UnionFind(N);for (int i = 0; i < M; i++) {int s, t;cin >> s >> t;s--; t--;table[s].push_back(t);table[t].push_back(s);uf.unite(s, t);}int Q;cin >> Q;for (int q = 0; q < Q; q++) {int a;cin >> a;a--;vector<bool> visited(N, false);visited[a] = true;queue<int> que;que.push(a);int dis = 0;vector<int> dis_v(N, 0);while (!que.empty()) {int node = que.front(); que.pop();for (int next : table[node]) {if (visited[next]) continue;dis = max(dis, dis_v[node] + 1);dis_v[next] = dis_v[node] + 1;que.push(next);visited[next] = true;}}cout << uf.get_forest_size(a) - 1 << " " << max(0LL, (int) ceil(log2(dis))) << endl;}return 0;}