Submission #1234370

#TimeUsernameProblemLanguageResultExecution timeMemory
1234370nasjesHotspot (NOI17_hotspot)C++20
9 / 100
19 ms17732 KiB
#include <iostream> #include <iomanip> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <stack> #include <bitset> #include <string> #include <cstring> #include <iterator> #include <random> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; const ll dim = 5*(1e3)+7; //const ll mod = 1e9 + 7; const ll inf = 1e18 + 77; #define endl "\n" #define fi first #define pb push_back #define se second #define vll vector<ll> ll n, m; ll t=0; vector<ll> a[dim]; ll tin[dim], tout[dim], depth[dim], sum[dim]; ll dst[dim][dim]; ll cntw[dim][dim]; int main() { cin>>n>>m; for(int i=1; i<=m; i++){ ll u, v, w; cin>>u>>v; u++; v++; a[u].pb(v); a[v].pb(u); } ll k; vector<pll> pr; cin>>k; for(int i=1; i<=k; i++){ ll u, v; cin>>u>>v; u++; v++; pr.pb({u, v}); } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ dst[i][j]=inf; } } for(int u=1; u<=n; u++){ queue<pll> q; dst[u][u]=0; q.push({u, 1}); while(q.size()>0){ ll v=q.front().fi; ll ways=q.front().se; q.pop(); if(ways<cntw[u][v]){ continue; } // vis[v]=1; for(auto x: a[v]){ ll cur=dst[u][v]+1; if(cur<dst[u][x]){ dst[u][x]=cur; cntw[u][x]=ways; q.push({x, ways}); } else if(cur==dst[u][x]){ dst[u][x]=cur; cntw[u][x]+=ways; q.push({x, cntw[u][x]}); } } } } ll id=1; ld ans=0; for(int e=1;e<=n; e++){ ld od=0; for(auto [u, v]: pr){ if(dst[e][u]+dst[e][v]!=dst[u][v])continue; ld cur=(ld)(cntw[e][u]*cntw[e][v])/((ld)cntw[u][v]); //cout<<fixed<<setprecision(10)<<cur<<endl; od+=cur; } if(od>ans){ ans=od; id=e; } } id--; cout<<id<<endl; return 0; }
#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...