結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2020-07-14 01:51:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 155 ms / 4,000 ms |
コード長 | 2,763 bytes |
コンパイル時間 | 2,284 ms |
コンパイル使用メモリ | 206,452 KB |
最終ジャッジ日時 | 2025-01-11 20:26:25 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h>#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define popcount __builtin_popcountusing ll = long long;constexpr ll mod = 1e9 + 7;constexpr ll INF = 1LL << 60;template <class T>inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}template <class T>inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}ll gcd(ll n, ll m){ll tmp;while (m != 0){tmp = n % m;n = m;m = tmp;}return n;}ll lcm(ll n, ll m){return abs(n) / gcd(n, m) * abs(m); //gl=xy}using namespace std;struct UF {vector<int>par;//親vector<int>Rank;//木の深さvector<int>sz;//要素数UF(int n){init(n);}//初期化void init(int n) {par.resize(n); Rank.resize(n);sz.resize(n);for (int i = 0; i < n; i++) {par[i]= i;Rank[i] = 0;sz[i]=1;}}//木の根を求めるint find(int x) {if (par[x] == x) {return x;}else {return par[x] = find(par[x]);}}//xとyの属する集合を併合bool unite(int x, int y) {x = find(x);y = find(y);if (x == y)return false;//すでに同じ集合に属しているif (Rank[x] < Rank[y]) {//高さが小さい方を下にpar[x] = y;sz[y]+=sz[x];}else {par[y] = x;if (Rank[x] == Rank[y])Rank[x]++;//同じだとrankが変わらないままになるので増やす(それ以外は大きい方のrankが採用される)sz[x]+=sz[y];}return true;}//xとyが同じ集合に属するかを判定bool same(int x, int y) {return find(x) == find(y);}int size(int k){//要素数を求めるreturn sz[find(k)];}};vector<vector<int>>g;void solve(){int n,m;cin>>n>>m;g.resize(n);UF tree(n);rep(i,m){int p,q;cin>>p>>q;p--;q--;g[p].pb(q);g[q].pb(p);tree.unite(p,q);}int q;cin>>q;while(q--){int a;cin>>a;a--;int x=tree.size(tree.find(a))-1;cout<<x<<" ";vector<int>dis(n,-1);queue<int>q;dis[a]=0;q.emplace(a);while(!q.empty()){int s=q.front();q.pop();for(auto e:g[s]){if(dis[e]==-1){dis[e]=dis[s]+1;q.emplace(e);}}}int val=1;int cnt=0;int v=*max_element(all(dis));while(val<v){val*=2;++cnt;}cout<<cnt<<"\n";}}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);solve();return 0;}