結果
問題 | No.922 東北きりきざむたん |
ユーザー | Rubikun |
提出日時 | 2019-11-08 22:12:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,639 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 174,996 KB |
実行使用メモリ | 26,112 KB |
最終ジャッジ日時 | 2024-09-15 01:32:46 |
合計ジャッジ時間 | 5,975 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,888 KB |
testcase_01 | AC | 4 ms
6,016 KB |
testcase_02 | AC | 4 ms
5,888 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 76 ms
16,000 KB |
testcase_29 | AC | 188 ms
26,112 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(x) (x).begin(),(x).end() const int mod=1000000007,MAX=100003,MAX_LOG=20,INF=1<<30; vector<int> G[MAX]; int seen[MAX],cnt[MAX]; int N,par[MAX_LOG][MAX],dis[MAX]; void BFS(int u){ queue<int> Q; Q.push(u); dis[u]=0; while(!Q.empty()){ int a=Q.front(); Q.pop(); for(int i=0;i<G[a].size();i++){ int b=G[a][i]; if(dis[b]==-1){ dis[b]=dis[a]+1; par[0][b]=a; Q.push(b); } } } return; } void init(){ for(int k=0;k+1<MAX_LOG;k++){ for(int i=0;i<N;i++){ if(par[k][i]<0) par[k+1][i]=-1; else par[k+1][i]=par[k][par[k][i]]; } } } int lca(int u,int v){ if(dis[u]>dis[v]) swap(u,v); for(int i=0;i<20;i++){ if(((dis[v]-dis[u])>>i)&1) v=par[i][v]; } if(u==v)return u; for(int i=19;i>=0;i--){ if(par[i][u]!=par[i][v]){ u = par[i][u]; v = par[i][v]; } } return par[0][u]; } int parrrr[MAX],size[MAX]; void UFinit(int n){ for(int i=0;i<n;i++){ parrrr[i]=i; size[i]=1; } } int root(int a){ if(parrrr[a]==a) return a; else return parrrr[a]=root(parrrr[a]); } void unite(int a,int b){ if(root(a)!=root(b)){ size[root(a)]+=size[root(b)]; parrrr[root(b)]=root(a); } } bool check(int a,int b){ return root(a)==root(b); } int cost[MAX],visited[MAX],mini[MAX]; void preDFS(int s,int u,int p){ visited[u]=1; for(int to:G[u]){ if(to==p) continue; preDFS(s,to,u); cnt[u]+=cnt[to]; cost[u]+=cnt[to]+cost[to]; } if(p==-1){ mini[s]=min(mini[s],cost[s]); } } int main(){ int M,Q;cin>>N>>M>>Q; UFinit(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); unite(a,b); } ll ans=0; for(int i=0;i<N;i++){ dis[i]=-1; mini[i]=INF; for(int j=0;j<20;j++){ par[j][i]=-1; } } for(int i=0;i<N;i++){ if(dis[i]==-1) BFS(i); } init(); for(int i=0;i<Q;i++){ int a,b;cin>>a>>b; a--;b--; if(check(a,b)){ ans+=dis[a]+dis[b]-2*dis[lca(a,b)]; }else{ cnt[a]++; cnt[b]++; } } for(int i=0;i<N;i++){ if(visited[i]==0){ preDFS(i,i,-1); ans+=mini[i]; } } cout<<ans<<endl; }