Submission #1165068

#TimeUsernameProblemLanguageResultExecution timeMemory
1165068DangKhoizzzzHotspot (NOI17_hotspot)C++20
38 / 100
86 ms21060 KiB
// 1 / 5 #include <bits/stdc++.h> #define int long long #define fi first #define se second #define pii pair <int , int> #define arr3 array <int , 3> /* + array limit ??? + special case ??? n = 1? + time limit ??? */ using namespace std; const int INF = 1e18 + 7; const int maxn = 5e3 + 7; vector <int> g[5005]; int n , k , m , f[5005][5005] , ways[5005][5005]; pii query[maxn]; void bfs(int st) { for(int i = 1; i <= n; i++) f[st][i] = INF; f[st][st] = 0; ways[st][st] = 1; vector <bool> vis(maxn , 0); queue <int> Q; Q.push(st); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(vis[u]) continue; vis[u] = 1; for(int v: g[u]) { if(f[st][v] > f[st][u] + 1) { f[st][v] = f[st][u] + 1; ways[st][v] = ways[st][u]; } else if(f[st][v] == f[st][u] + 1) { ways[st][v] += ways[st][u]; } if(!vis[v]) Q.push(v); } } } pair <double , int> ans = {-1 , -1}; void solve() { cin >> n >> m; for(int i = 1; i <= m; i++) { int u , v; cin >> u >> v; u++, v++; g[u].push_back(v); g[v].push_back(u); } for(int i = 1; i <= n; i++) {bfs(i);} cin >> k; for(int i = 1; i <= k; i++) { cin >> query[i].fi >> query[i].se; query[i].fi++ , query[i].se++; } for(int u = 1; u <= n; u++) { int total = 0 , sum = 0; for(int i = 1; i <= k; i++) { if(f[query[i].fi][u] + f[u][query[i].se] == f[query[i].fi][query[i].se]) { sum += ways[query[i].fi][u] * ways[query[i].se][u]; } total += ways[query[i].fi][query[i].se]; } ans = max(ans , {((double)(1.0 * sum )/ total) , u}); } cout << ans.se - 1 << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("inp.txt" , "r" , stdin); //freopen("out.txt" , "w" , stdout); solve(); 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...