Submission #684468

#TimeUsernameProblemLanguageResultExecution timeMemory
684468dsyzHotspot (NOI17_hotspot)C++17
100 / 100
734 ms1516 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = double; #define MAXN (1000005) int main(){ ios_base::sync_with_stdio(false);cin.tie(0); ll N,M; cin>>N>>M; vector<ll> v[N]; for(ll i = 0;i < M;i++){ ll a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } ll K; cin>>K; queue<ll> q; ld ans[N]; memset(ans,0,sizeof(ans)); pair<ll,ll> dist1[N]; pair<ll,ll> dist2[N]; for(ll person = 0;person < K;person++){ ll A,B; cin>>A>>B; for(ll i = 0;i < N;i++) dist1[i] = {1e9 + 5,0}; q.push(A); dist1[A] = {0,1}; while(!q.empty()){ ll x = q.front(); q.pop(); for(auto u : v[x]){ if(dist1[x].first + 1 < dist1[u].first){ q.push(u); dist1[u] = {dist1[x].first + 1,dist1[x].second}; }else if(dist1[x].first + 1 == dist1[u].first){ dist1[u].second += dist1[x].second; } } } for(ll i = 0;i < N;i++) dist2[i] = {1e9 + 5,0}; q.push(B); dist2[B] = {0,1}; while(!q.empty()){ ll x = q.front(); q.pop(); for(auto u : v[x]){ if(dist2[x].first + 1 < dist2[u].first){ q.push(u); dist2[u] = {dist2[x].first + 1,dist2[x].second}; }else if(dist2[x].first + 1 == dist2[u].first){ dist2[u].second += dist2[x].second; } } } for(ll i = 0;i < N;i++){ if(dist1[i].first + dist2[i].first == dist1[B].first){ ans[i] += ld(dist1[i].second * dist2[i].second) / ld(dist1[B].second); } } } ld maximum = -1e18; ll index = 0; for(ll i = 0;i < N;i++){ if(ans[i] > maximum){ maximum = ans[i]; index = i; } } cout<<index<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...