Submission #738173

#	Time	Username	Problem	Language	Result	Execution time	Memory
738173		Ronin13	Hotspot (NOI17_hotspot)	C++14	100 / 100	900 ms	7032 KiB

hotspot

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 200001;

vector <vector <int>  > g(nmax);
vector <double> ans(nmax);
int n;

void BFS(int a, int b){
    queue <int> q;
    vector <int> dp(n + 1, 0);
    dp[a] = 1;
    vector <int> d(n + 1, 1e9);
    d[a] = 0;
    q.push(a);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int to : g[v]){
            if(d[to] == d[v]) continue;
            if(d[to] > d[v]) dp[to] += dp[v];
            if(d[to] == 1e9) d[to] = d[v] + 1, q.push(to);
        }
    }
    int x = d[b];
    vector <int> DP(n + 1, 0);
    swap(a, b);
    DP[a] = 1;
    vector <int> D(n + 1, 1e9);
    D[a] = 0;
    q.push(a);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int to : g[v]){
            if(D[to] <= D[v]) continue;
            if(D[to] > D[v]) DP[to] += DP[v];
            if(D[to] == 1e9) D[to] = D[v] + 1, q.push(to);
        }
    }
    for(int i = 0; i < n; ++i){
        if(d[i] + D[i] != x) continue;
        double x = dp[i] * DP[i];
       // cout << x << ' ';
        double t = DP[a] * dp[a];
        ans[i] += x / t;
    }
  //  cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int  m; cin >> n >> m;
    int k;
    for(int i= 1; i <= m; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> k;
    for(int i = 1; i <= k; i++){
        int a, b; cin >> a >> b;
        BFS(a, b);
    }
    double mx = 0, mxi = 0;
    for(int i = 0; i < n; i++){
        //cout << ans[i] << "\n";
        if(ans[i] > mx)
            mx = ans[i], mxi = i;
    }
    cout << mxi;
}

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