Submission #1239539

#TimeUsernameProblemLanguageResultExecution timeMemory
1239539eirinayukariHotspot (NOI17_hotspot)C++20
100 / 100
933 ms1040 KiB
// XD XD #include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define el cout << "\n"; using namespace std; using ll = long long; const int MAXN = 5000 + 7; const int MAXK = 2000 + 7; const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const ll LLINF = 1e18 + 7; template <typename T> bool ckmin(T& a, T b) { return a > b ? a = b, true : false; } template <typename T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; } int n, m, k; int a[MAXK], b[MAXK]; int bdist[MAXK], bways[MAXK]; int dist[MAXN], ways[MAXN]; vector<int> adj[MAXN]; queue<int> q; void bfs(int u) { for (int i = 1; i <= n; i++) { dist[i] = INF; ways[i] = 0; } q = {}; dist[u] = 0; ways[u] = 1; q.push(u); while (q.size()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] > dist[u] + 1) { dist[v] = dist[u] + 1; ways[v] = ways[u]; q.push(v); } else if (dist[v] == dist[u] + 1) { ways[v] += ways[u]; } } } } void solve(int id) { // cout << "Case " << id << ": "; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; u++; v++; adj[u].push_back(v); adj[v].push_back(u); } cin >> k; for (int i = 1; i <= k; i++) { cin >> a[i] >> b[i]; a[i]++; b[i]++; } for (int i = 1; i <= k; i++) { bfs(a[i]); bdist[i] = dist[b[i]]; bways[i] = ways[b[i]]; } double expv = -INF; int ans = 0; for (int i = 1; i <= n; i++) { double expi = 0; bfs(i); for (int j = 1; j <= k; j++) { int tot = dist[a[j]] + dist[b[j]]; if (tot == bdist[j]) { expi += 1.0 * (ways[a[j]] * ways[b[j]]) / bways[j]; } } if (ckmax(expv, expi)) { ans = i; } } cout << ans - 1 << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); int T = 1; // cin >> T; for (int i = 1; i <= T; i++) { solve(i); } 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...