Submission #1165063

#TimeUsernameProblemLanguageResultExecution timeMemory
1165063DangKhoizzzzHotspot (NOI17_hotspot)C++20
0 / 100
10 ms17220 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; queue <int> Q; Q.push(st); while(!Q.empty()) { int u = Q.front(); Q.pop(); 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]; Q.push(v); } else if(f[st][v] == f[st][u] + 1) { ways[st][v] += ways[st][u]; } } } } 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; } for(int u = 1; u <= n; u++) { int total = 0 , sum = 0; bool check = 1; 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]) { check = 0; break; } sum += ways[query[i].fi][u] * ways[query[i].se][u]; total += ways[query[i].fi][query[i].se]; } if(check) { 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); 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...