結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-21 18:21:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 4,000 ms |
コード長 | 3,534 bytes |
コンパイル時間 | 1,955 ms |
コンパイル使用メモリ | 178,380 KB |
実行使用メモリ | 11,524 KB |
最終ジャッジ日時 | 2024-06-12 20:56:04 |
合計ジャッジ時間 | 7,502 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#define _USE_MATH_DEFINES#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>using namespace std;/*BigInteger#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>#include <boost/rational.hpp>namespace xxx = boost::multiprecision;using Bint = xxx::cpp_int;using Real = xxx::number<xxx::cpp_dec_float<1024>>;*/#define int long long#define pb(x) push_back(x)#define m0(x) memset((x), 0, sizeof(x))#define mm(x) memset((x), -1, sizeof(x))//container#define ALL(x) (x).begin(), (x).end()#define RALL(a) (a).rbegin(), (a).rend()#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)#define EXIST(s, e) ((s).find(e) != (s).end())#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());#define PERM(c) \sort(ALL(c)); \for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))// debug#define GET_VAR_NAME(variable) #variable#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;// bit_macro#define bit(n) (1LL << (n))#define bitset(a, b) (a) |= (1 << (b))#define bitunset(a, b) (a) &= ~(1 << (b))#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)#define bitcount(a) __builtin_popcountll((a))//typedeftypedef long long lint;typedef unsigned long long ull;typedef complex<long double> Complex;typedef pair<int, int> P;typedef tuple<int, int, int> TP;typedef vector<int> vec;typedef vector<vec> mat;//constantconstexpr int INF = (int)1e18;constexpr int MOD = (int)1e9 + 7;constexpr double PI = (double)acos(-1);constexpr double EPS = (double)1e-10;constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};//template <typename T>void chmax(T &a, T b) { a = max(a, b); }template <typename T>void chmin(T &a, T b) { a = min(a, b); }//inline int toInt(string s) {int v;istringstream sin(s);sin >> v;return v;}template <class T>inline string toString(T x) {ostringstream sout;sout << x;return sout.str();}//struct Accelerate_Cin {Accelerate_Cin() {cin.tie(0);ios::sync_with_stdio(0);cout << fixed << setprecision(20);};};struct UnionFind {vector<int> data;UnionFind(int sz) {data.assign(sz, -1);}bool same(int x, int y) {return find(x) == find(y);}bool unite(int x, int y) {x = find(x), y = find(y);if (x == y) return (false);if (data[x] > data[y]) swap(x, y);data[x] += data[y];data[y] = x;return (true);}int find(int k) {if (data[k] < 0) return (k);return (data[k] = find(data[k]));}int size(int k) {return (-data[find(k)]);}};int N, M, Q;vector<int> G[101010];int bfs(int s) {vec d(101010, INF);vector<bool> vis(101010, 0);d[s] = 0;vis[s] = true;queue<int> q;q.push(s);int ans = 0;while (!q.empty()) {int t = q.front();q.pop();for (auto x : G[t]) {if (vis[x] == false) {d[x] = d[t] + 1;vis[x] = true;chmax(ans, d[x]);q.push(x);}}}return ans;}signed main() {cin >> N >> M;UnionFind uf(N);for (int i = 0; i < M; i++) {int p, q;cin >> p >> q;p--, q--;G[p].push_back(q);G[q].push_back(p);uf.unite(p, q);}cin >> Q;while (Q--) {int a;cin >> a;a--;int day = 0;int k = bfs(a);int tmp = 1;while (tmp < k) {tmp *= 2;day++;}cout << uf.size(a) - 1 << " " << day << endl;}return 0;}