結果

問題 No.812 Change of Class
ユーザー dsm4up2cdsm4up2c
提出日時 2019-04-13 04:44:38
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 209 ms / 4,000 ms
コード長 2,173 bytes
コンパイル時間 1,026 ms
コンパイル使用メモリ 84,504 KB
実行使用メモリ 10,464 KB
最終ジャッジ日時 2024-06-12 20:21:40
合計ジャッジ時間 7,176 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define all(x) x.begin(),x.end()
const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;
struct union_find{
vector<int> par,r,size;
union_find(int n) : par(n),r(n),size(n){init(n);}
void init(int n){
for(int i = 0; i < n; i++) par[i] = i;
for(int i = 0; i < n; i++) r[i] = 0;
for(int i = 0; i < n; i++) size[i] = 1;
}
int find(int x){
if(par[x] == x) return x;
else return find(par[x]);
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y) return;
if(r[x] < r[y]){
par[x] = y;
size[y] += size[x];
}else{
par[y] = x;
size[x] += size[y];
if(r[x] == r[y]) r[x]++;
}
}
bool same(int x,int y){
return find(x) == find(y);
}
};
vector<vector<int> > g;
vector<int> dist;
int main()
{
int n,m;
cin>>n>>m;
g.resize(n);
dist.resize(n);
union_find uf(n);
for(int i = 0; i < m; i++){
int a,b;
cin>>a>>b;
a--;b--;
g[a].push_back(b);
g[b].push_back(a);
uf.unite(a,b);
}
int q;
cin>>q;
for(int i = 0; i < q; i++){
int a;
cin>>a;
a--;
dist.assign(dist.size(),INF);
queue<int> que;
que.push(a);
dist[a] = 0;
while(!que.empty()){
int x = que.front();que.pop();
for(int i = 0; i < g[x].size(); i++){
if(dist[x]+1<dist[g[x][i]]){
dist[g[x][i]] = dist[x]+1;
que.push(g[x][i]);
}
}
}
int max_dist = 0;
for(int i = 0; i < n; i++){
if(max_dist<dist[i] && dist[i]<INF) max_dist = dist[i];
}
int l = 0;
max_dist--;
while(max_dist>0){
max_dist /= 2;
l++;
}
cout << uf.size[uf.find(a)]-1 << " " << l <<endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0