Submission #334471

#TimeUsernameProblemLanguageResultExecution timeMemory
334471ncduy0303Hotspot (NOI17_hotspot)C++17
100 / 100
827 ms250988 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define ll long long const int MAX_N = 5e3 + 1; const int MOD = 1e9 + 7; const int INF = 1e9; const ll LINF = 1e18; int n, m, k; vector<int> adj[MAX_N]; ll dist[MAX_N][MAX_N], cnt[MAX_N][MAX_N]; double p[MAX_N]; void bfs(int s) { queue<ar<int,2>> q; q.push({0, s}); dist[s][s] = 0; cnt[s][s] = 1; while (!q.empty()){ auto [d, u] = q.front(); q.pop(); if (d > dist[s][u]) continue; for (int v : adj[u]) { if (dist[s][v] > dist[s][u] + 1) { dist[s][v] = dist[s][u] + 1; cnt[s][v] = cnt[s][u]; q.push({dist[s][v], v}); } else if (dist[s][v] == dist[s][u] + 1) { cnt[s][v] += cnt[s][u]; } } } } void solve() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } memset(dist, 0x3f, sizeof dist); cin >> k; while (k--) { int u, v; cin >> u >> v; if (dist[u][u] > 0) bfs(u); if (dist[v][v] > 0) bfs(v); for (int i = 0; i < n; i++) { if (dist[u][v] == dist[u][i] + dist[v][i]) { p[i] += (double)(cnt[u][i] * cnt[v][i]) / cnt[u][v]; } } } int ans = 0; for (int i = 0; i < n; i++) { if (p[i] > p[ans]) { ans = i; } } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tc = 1; // cin >> tc; for (int t = 1; t <= tc; t++) { // cout << "Case #" << t << ": "; solve(); } }

Compilation message (stderr)

hotspot.cpp: In function 'void bfs(int)':
hotspot.cpp:29:22: warning: narrowing conversion of 'dist[s][v]' from 'long long int' to 'int' [-Wnarrowing]
   29 |     q.push({dist[s][v], v});
      |             ~~~~~~~~~^
#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...