Submission #949937

#	Time	Username	Problem	Language	Result	Execution time	Memory
949937		efishel	Hotspot (NOI17_hotspot)	C++17	100 / 100	413 ms	2644 KiB

hotspot

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using dou = double;
using vll = vector <ll>;

const ll MAXN = 5E3+16;
vll adj[MAXN];
vll radj[MAXN];

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    for (ll i = 0; i < m; i++) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ll k;
    cin >> k;
    vector <dou> vals(n, 0);
    for (ll i = 0; i < k; i++) {
        ll s, t;
        cin >> s >> t;
        for (ll j = 0; j < MAXN; j++) radj[j].clear();
        vll dp1(n, 0); // ways to reach i from s (s -> i)
        vll dp2(n, 0); // ways to reach t from i (i -> t)
        vll dis(n, -16);
        {vector <bool> vis(n, false);
        queue <ll> q;
        dp1[s] = 1;
        q.push(s);
        dis[s] = 0;
        vis[s] = true;
        while (q.size()) { // count shortest paths
            ll u = q.front(); q.pop();
            // cerr << u << '\n';
            for (ll v : adj[u]) {
                if (vis[v] && dis[u]+1 != dis[v]) continue;
                // cerr << "   " << v << '\n';
                dp1[v] += dp1[u];
                radj[v].push_back(u);
                if (vis[v]) continue;
                // cerr << "   new\n";
                q.push(v);
                dis[v] = dis[u]+1;
                vis[v] = true;
            }
        }}
        // // for (ll i : dp1) cerr << i << ' '; cerr << '\n';
        {vector <bool> vis(n, false); // travel from t to s adding values
        queue <ll> q;
        q.push(t);
        assert(dp1[t] > 0);
        dp2[t] = 1;
        while (q.size()) {
            ll u = q.front(); q.pop();
            // cerr << u << '\n';
            vals[u] += dou(dp1[u] * dp2[u]) / dou(dp1[t] * dp2[t]);
            for (ll v : radj[u]) {
                if (dis[u]-1 != dis[v]) continue;
                // cerr << "   " << v << '\n';
                dp2[v] += dp2[u];
                if (vis[v]) continue;
                // cerr << "   new\n";
                q.push(v);
                vis[v] = true;
            }
        }}
        // // for (ll i : dp2) cerr << i << ' '; cerr << '\n';
    }
    // cerr << fixed << setprecision(6);
    // for (dou i : vals) cerr << i << ' ';
    // cerr << '\n';
    cout << max_element(vals.begin(), vals.end()) - vals.begin() << '\n';
    return 0;
}

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