# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672946 | vuavisao | Hotspot (NOI17_hotspot) | C++14 | 843 ms | 1260 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define ld long double
using namespace std;
template<typename Lhs, typename Rhs> inline bool Max_self(Lhs &a, Rhs b) { if(b > a) { a = b; return true; } return false; }
template<typename Lhs, typename Rhs> inline bool Min_self(Lhs &a, Rhs b) { if(b < a) { a = b; return true; } return false; }
const int N = 5e3 + 10;
const int INF = 1e9;
int n, m, q;
vector<int> g[N];
int dist[2][N];
ld cnt[2][N];
ld res[N];
void Dijkstra(int u, int* dist, ld* cnt);
void Dijkstra(int u, int* dist, ld* cnt) {
for(int i = 1; i <= n; ++ i) {
dist[i] = INF;
cnt[i] = 0;
}
dist[u] = 0; cnt[u] = 1;
queue<int> q = {};
q.push(u);
while(!q.empty()) {
int u = q.front(); q.pop();
for(const auto& v : g[u]) {
if(Min_self(dist[v], dist[u] + 1)) {
cnt[v] = cnt[u];
q.push(v);
}
else if(dist[v] == dist[u] + 1) {
cnt[v] += cnt[u];
}
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("NOI17_hotspot.inp", "r")) {
freopen("NOI17_hotspot.inp", "r", stdin);
freopen("NOI17_hotspot.out", "w", stdout);
}
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);
}
cin >> q;
while(q--) {
int u, v; cin >> u >> v; ++ u; ++ v;
Dijkstra(u, dist[0], cnt[0]);
Dijkstra(v, dist[1], cnt[1]);
for(int i = 1; i <= n; ++ i) {
// cout << dist[0][i] << ' ' << dist[1][i] << '\n';
if(dist[0][i] + dist[1][i] == dist[0][v]) {
res[i] += cnt[0][i] * cnt[1][i] / cnt[0][v];
}
}
}
cout << max_element(res + 1, res + 1 + n) - res - 1;
return 0;
}
/// Code by vuavisao
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |