結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 2019-04-13 17:35:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 527 ms / 4,000 ms |
コード長 | 3,411 bytes |
コンパイル時間 | 1,937 ms |
コンパイル使用メモリ | 181,944 KB |
実行使用メモリ | 15,144 KB |
最終ジャッジ日時 | 2024-06-12 20:34:46 |
合計ジャッジ時間 | 12,452 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include<bits/stdc++.h>using namespace std;class UnionFind{public://親の番号を格納する。親だった場合は-(その集合のサイズ)vector<int> parent;//-1で初期化//最初はすべてバラバラUnionFind(int N){parent = vector<int>(N,-1);}//Aがどのグループに属しているか(Aの根)を調べるint root(int A){if(parent[A] < 0) return A;return parent[A]=root(parent[A]);}//自分のいるグループの頂点数を調べるint size(int A){return -parent[root(A)];}//AとBをくっつけるbool connect(int A, int B) {//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつけるA = root(A);B = root(B);//既にくっついているからくっつけないif(A == B) return false;//大きいほう(A)に小さいほう(B)をくっつける//大小が逆ならひっくり返すif(size(A) < size(B)) swap(A,B);//Aのサイズを更新するparent[A] += parent[B];//Bの親をAに変更するparent[B] = A;return true;}//AとBが同じグループならtrueを返すbool same(int A, int B){return root(A)==root(B);}};class Dijkstra {public:struct edge { long long v, dist; };struct state {long long v, cost;bool operator>(const state s) const { return cost > s.cost; }};const long long INF = (1LL << 60);long long N;vector< vector<edge> > E;Dijkstra(long long n): N(n), E(n) {}//有効グラフの時はこっち。u→vに距離dで結ぶvoid add_directed_edge(long long u, long long v, long long d) {E[u].push_back((edge) { v, d });}//無向グラフの時はこっち。uとvを双方向に距離dで結ぶvoid add_undirected_edge(long long u, long long v, long long d) {E[u].push_back((edge) { v, d });E[v].push_back((edge) { u, d });}//Sを始点として、他の頂点への最短経路を探すvector<long long> shortest_path(long long S) {vector<long long> dp(E.size(), INF);priority_queue<state, vector<state>, greater<state> > q;q.push((state) { S, 0 });while(!q.empty()) {long long v = q.top().v, cost = q.top().cost;q.pop();if(dp[v] <= cost) continue;dp[v] = cost;for(int i=0;i < E[v].size() ; i++) {long long nv = E[v][i].v, ncost = cost + E[v][i].dist;if(dp[nv] > ncost) q.push((state) { nv, ncost });}}return dp;}};int main(){int n,m;cin>>n>>m;int p[m],q[m];UnionFind uni(n);Dijkstra di(n);for(int i=0;i<m;i++){cin>>p[i]>>q[i];p[i]--;q[i]--;uni.connect(p[i],q[i]);di.add_undirected_edge(p[i],q[i],1);}int Q;cin>>Q;int a;for(int i=0;i<Q;i++){cin>>a;a--;cout<<uni.size(a)-1<<" ";long long ans=0;const long long INF = (1LL << 60);vector<long long> v=di.shortest_path(a);for(int i=0;i<n;i++){if(v[i]!=INF) ans=max(ans,v[i]);}int t=0;for(;pow(2,t)<ans;t++);cout<<t<<endl;}}