Submission #1102934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102934		icebear	Hotspot (NOI17_hotspot)	C++17	38 / 100	9 ms	74320 KiB

hotspot

// ~~ icebear & at~~
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5000 + 5;
int numNode, numEdge, numQuery;
vector<int> G[N];
int dist[N][N], ways[N][N];
bool computed[N];
queue<int> Q;
int a[N], b[N];

void BFS(int x) {
    memset(dist[x], 0x3f, sizeof dist[x]);
    dist[x][x] = 0;
    ways[x][x] = 1;
    Q.push(x);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int v : G[u])
            if (dist[x][v] > dist[x][u] + 1) {
                dist[x][v] = dist[x][u] + 1;
                ways[x][v] = ways[x][u];
                Q.push(v);
            } else if (dist[x][v] == dist[x][u] + 1)
                ways[x][v] = ways[x][u] + 1;
    }
}

bool isLarger(array<int, 3> &x, array<int, 3> &y) {
    return 1ll * x[0] * y[1] > 1ll * x[1] * y[0];
}

signed main(){
    // freopen("TRAINCENTRE.inp", "r", stdin);
    // freopen("TRAINCENTRE.out", "w", stdout);
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin >> numNode >> numEdge;
    for(int i = 0; i < numEdge; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    cin >> numQuery;
    for(int i = 0; i < numQuery; i++) {
        cin >> a[i] >> b[i];
        if (!computed[a[i]]) {
            BFS(a[i]);
            computed[a[i]] = true;
        }
        if (!computed[b[i]]) {
            BFS(b[i]);
            computed[b[i]] = true;
        }
    }

    array<int, 3> ans = {0, 1, 0};
    for(int w = 0; w < numNode; w++) {
        int fixedPath = 0, totalPath = 0;
        for(int i = 0; i < numQuery; i++) {
            if (dist[a[i]][w] + dist[b[i]][w] == dist[a[i]][b[i]]) 
                fixedPath += ways[a[i]][w] * ways[b[i]][w];
            totalPath += ways[a[i]][b[i]];
        }

        int g = __gcd(fixedPath, totalPath);
        array<int, 3> tmp = {fixedPath / g, totalPath / g, w};
        if (isLarger(tmp, ans)) ans = tmp;        
    }
    
    cout << ans[2];
    return 0;
}

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