Submission #1102946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102946		Cam	Hotspot (NOI17_hotspot)	C++17	100 / 100	1055 ms	1104 KiB

hotspot

#include <bits/stdc++.h>
#define name "traincentre"
#define ll long long
#define db double
#define pb push_back
#define ii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define bit(x,i) (((x)>>(i))&1)
#define sz(s) (int)(s).size()
#define all(a) (a).begin(),(a).end()
#define rep(i,a,b) for(int i=(a), _b=(b); i<=_b; i++)
#define repd(i,a,b) for(int i=(a), _b=(b); i>=_b; i--)
#define _unique(x) (x).resize(unique(all(x)) - (x).begin())

using namespace std;

const int N = 5e3 + 3;
const int inf = 1e9 + 7;
const int base = 31;
const double eps = 0.00000001;

int n, m, k;
int d[2][N];
db cnt[2][N], ans[N], res;
vector <int> a[N];

void dijkstra (int o, int s) {

    rep (i, 1, n) d[o][i] = inf, cnt[o][i] = 0;
    priority_queue <ii, vector <ii>, greater <ii> > q;
    q.push (mp (0, s)); d[o][s] = 0; cnt[o][s] = 1;

    while (sz (q)) {

        int u = q.top().se, du = q.top().fi; q.pop();
        if (du > d[o][u]) continue;
        for (int v : a[u]) {

            if (d[o][v] > d[o][u] + 1) {

                d[o][v] = d[o][u] + 1;
                q.push (mp (d[o][v], v));
                cnt[o][v] = cnt[o][u];
            }
            else if (d[o][v] == d[o][u] + 1) cnt[o][v] += cnt[o][u];
        }
    }
}
void solve (void) {

    cin >> n >> m;
    rep (i, 1, m) {

        int u, v; cin >> u >> v;
        u ++; v ++;
        a[u].pb (v); a[v].pb (u);
    }
    cin >> k;
    rep (i, 1, k) {

        int x, y;
        cin >> x >> y;
        x ++; y ++;
        dijkstra (0, x); dijkstra (1, y);
        rep (u, 1, n) if (d[0][u] + d[1][u] == d[0][y]) {

            db tmp = (db)(cnt[0][u] * cnt[1][u]);
            tmp = tmp / (db)cnt[0][y];
            ans[u] += tmp;
        }
    }
    int u = 1; res = ans[1];
    rep (i, 2, n) if (ans[i] > res) {

        res = ans[i];
        u = i;
    }
    cout << u - 1;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(name".inp","r",stdin);
    //freopen(name".out","w",stdout);

    solve();
    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