結果

問題 No.812 Change of Class
ユーザー totori_nyaatotori_nyaa
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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)];
}
//AB
bool connect(int A, int B) {
//ABroot(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];
//BA
parent[B] = A;
return true;
}
//ABtrue
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→vd
void add_directed_edge(long long u, long long v, long long d) {
E[u].push_back((edge) { v, d });
}
//uvd
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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0