結果
問題 | No.812 Change of Class |
ユーザー | totori_nyaa |
提出日時 | 2019-04-13 17:35:47 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 575 ms / 4,000 ms |
コード長 | 3,411 bytes |
コンパイル時間 | 1,970 ms |
コンパイル使用メモリ | 179,768 KB |
実行使用メモリ | 14,980 KB |
最終ジャッジ日時 | 2023-09-03 14:51:25 |
合計ジャッジ時間 | 14,355 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 97 ms
10,696 KB |
testcase_01 | AC | 15 ms
4,492 KB |
testcase_02 | AC | 52 ms
7,464 KB |
testcase_03 | AC | 114 ms
11,812 KB |
testcase_04 | AC | 101 ms
10,920 KB |
testcase_05 | AC | 575 ms
13,196 KB |
testcase_06 | AC | 548 ms
13,088 KB |
testcase_07 | AC | 5 ms
4,812 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 515 ms
13,700 KB |
testcase_10 | AC | 529 ms
13,748 KB |
testcase_11 | AC | 22 ms
7,568 KB |
testcase_12 | AC | 279 ms
11,876 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 320 ms
10,128 KB |
testcase_16 | AC | 18 ms
4,380 KB |
testcase_17 | AC | 308 ms
10,700 KB |
testcase_18 | AC | 204 ms
8,684 KB |
testcase_19 | AC | 228 ms
9,424 KB |
testcase_20 | AC | 563 ms
13,480 KB |
testcase_21 | AC | 185 ms
8,456 KB |
testcase_22 | AC | 83 ms
6,012 KB |
testcase_23 | AC | 14 ms
4,384 KB |
testcase_24 | AC | 21 ms
4,380 KB |
testcase_25 | AC | 63 ms
5,220 KB |
testcase_26 | AC | 433 ms
11,564 KB |
testcase_27 | AC | 357 ms
10,796 KB |
testcase_28 | AC | 232 ms
9,488 KB |
testcase_29 | AC | 47 ms
4,744 KB |
testcase_30 | AC | 316 ms
10,500 KB |
testcase_31 | AC | 264 ms
9,324 KB |
testcase_32 | AC | 102 ms
6,136 KB |
testcase_33 | AC | 335 ms
11,224 KB |
testcase_34 | AC | 20 ms
4,376 KB |
testcase_35 | AC | 46 ms
4,968 KB |
testcase_36 | AC | 20 ms
4,376 KB |
testcase_37 | AC | 120 ms
6,476 KB |
testcase_38 | AC | 8 ms
5,364 KB |
testcase_39 | AC | 128 ms
6,360 KB |
testcase_40 | AC | 28 ms
4,452 KB |
testcase_41 | AC | 7 ms
4,928 KB |
testcase_42 | AC | 271 ms
9,388 KB |
testcase_43 | AC | 43 ms
7,232 KB |
testcase_44 | AC | 187 ms
7,840 KB |
testcase_45 | AC | 21 ms
4,380 KB |
testcase_46 | AC | 38 ms
7,492 KB |
testcase_47 | AC | 178 ms
7,824 KB |
testcase_48 | AC | 187 ms
8,744 KB |
testcase_49 | AC | 53 ms
4,996 KB |
testcase_50 | AC | 3 ms
4,380 KB |
testcase_51 | AC | 48 ms
5,400 KB |
testcase_52 | AC | 94 ms
7,928 KB |
testcase_53 | AC | 36 ms
4,608 KB |
testcase_54 | AC | 31 ms
4,416 KB |
testcase_55 | AC | 158 ms
11,268 KB |
testcase_56 | AC | 207 ms
13,248 KB |
testcase_57 | AC | 218 ms
14,004 KB |
testcase_58 | AC | 107 ms
8,592 KB |
testcase_59 | AC | 242 ms
14,980 KB |
testcase_60 | AC | 1 ms
4,380 KB |
testcase_61 | AC | 1 ms
4,380 KB |
testcase_62 | AC | 2 ms
4,380 KB |
ソースコード
#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; } }