Submission #684447

#TimeUsernameProblemLanguageResultExecution timeMemory
684447dsyzHotspot (NOI17_hotspot)C++17
38 / 100
10 ms596 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; pair<ll,ll> arr[K]; for(ll i = 0;i < K;i++){ cin>>arr[i].first>>arr[i].second; } 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 = arr[person].first; ll B = arr[person].second; for(ll i = 0;i < N;i++) dist1[i] = {-1,0}; q.push(A); dist1[A] = {0,1}; while(!q.empty()){ ll x = q.front(); q.pop(); for(auto u : v[x]){ if(dist1[u].first == -1 || dist1[x].first + 1 < dist1[u].first){ q.push(u); dist1[u] = {dist1[x].first + 1,1}; }else if(dist1[x].first + 1 == dist1[u].first){ q.push(u); dist1[u].second += dist1[x].second; } } } for(ll i = 0;i < N;i++) dist2[i] = {-1,0}; q.push(B); dist2[B] = {0,1}; while(!q.empty()){ ll x = q.front(); q.pop(); for(auto u : v[x]){ if(dist2[u].first == -1 || dist2[x].first + 1 < dist2[u].first){ q.push(u); dist2[u] = {dist2[x].first + 1,1}; }else if(dist2[x].first + 1 == dist2[u].first){ q.push(u); 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 = 0; 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...