Submission #1109514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109514		kh0i	Hotspot (NOI17_hotspot)	C++17	100 / 100	597 ms	1360 KiB

hotspot

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 5003;

int n, m;
vector<int> g[N];
int k;
int a[N], b[N];

int d1[N], d2[N];
double f1[N], f2[N], tot[N];

void bfs(int src, int dist[], double f[]){
    for(int i = 0; i < n; ++i)
        f[i] = 0, dist[i] = -1;
    dist[src] = 0;
    f[src] = 1;
    queue<int> q;
    q.push(src);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : g[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] + 1;
                f[v] = f[u];
                q.push(v);
            }
            else if(dist[v] == dist[u] + 1)
                f[v] += f[u];
        }
    }
}


void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> k;
    for(int i = 0; i < k; ++i)
        cin >> a[i] >> b[i];
    for(int i = 0; i < k; ++i){
        bfs(a[i], d1, f1);
        bfs(b[i], d2, f2);
        for(int u = 0; u < n; ++u){
            if(d1[u] != -1 and d2[u] != -1 and d1[u] + d2[u] == d1[b[i]]){
                debug(a[i], b[i], u);
                tot[u] += (f1[u] * f2[u]) / f1[b[i]];
            }
        }
    }

    int res = -1;
    for(int i = 0; i < n; ++i){
        debug(i, tot[i]);
        if(res == -1 or tot[res] < tot[i])
            res = i;
    }

    cout << res;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "traincentre"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message (stderr)

hotspot.cpp: In function 'int32_t main()':
hotspot.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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