Submission #1122939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122939		mingga	Hotspot (NOI17_hotspot)	C++17	100 / 100	541 ms	109064 KiB

hotspot

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int MOD = 1e9 + 7;
const int inf = 2e18;
const int N = 5005;
int n, m, k, f[N][N], cnt[N][N];

pair<int, int> d[N];    

double h[N];    

vector<int> g[N];

void bfs(int st) {
    for(int i = 1; i <= n; i++) f[st][i] = inf;
    f[st][st] = 0;
    cnt[st][st] = 1;
    queue<int> q;
    q.push(st);
    while(sz(q)) {
        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;
                cnt[st][v] = cnt[st][u];
                q.push(v);
            } else if(f[st][v] == f[st][u] + 1) {
                cnt[st][v] += cnt[st][u];
            }
        }
    }
}

bool mark[N];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        u++, v++;
        g[u].pb(v);
        g[v].pb(u); 
    }
    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> d[i].fi >> d[i].se;
        d[i].fi++, d[i].se++;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            int a = d[j].fi, b = d[j].se;
            if(mark[a] == 0) bfs(a);
            if(mark[b] == 0) bfs(b);
            mark[a] = mark[b] = 1;
            if(f[a][i] + f[b][i] == f[a][b]) {
                int sus = cnt[a][i] * cnt[b][i];
                h[i] += (double) sus / cnt[a][b];   
            }
        }
        if(h[i] > h[ans]) {
            ans = i;
        }
    }
    cout << ans - 1;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36