Submission #1105381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105381		monaxia	Hotspot (NOI17_hotspot)	C++17	64 / 100	361 ms	524288 KiB

hotspot

// credit: Mai Hong Kien
 
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll LIMIT = 2e3 + 5;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random (ll l, ll r){return uniform_int_distribution <ll> (l, r)(rng);}
 
 
void solve(){
    ll n, m;
    long double mx = 0, res = 0;
    cin >> n >> m;
 
    vector <vector <ll>> graph(n + 1), dist(n + 1, vector <ll> (n + 1, INT_MAX)), path(n + 1, vector <ll> (m + 1, 0));
    vector <long double> e(n + 1, 0);
    vector <pair <ll, ll>> range;
 
    for(ll i = 1; i <= m; i ++){
        ll u, v;
        cin >> u >> v;
 
        graph[u].pb(v);
        graph[v].pb(u);
    }
 
    for(ll i = 0; i < n; i ++){
        dist[i][i] = 0;
        path[i][i] = 1;
 
        vector <ll> v(n + 1, 0);
        queue <ll> q;
 
        q.push(i);
 
        while(!q.empty()){
            ll s = q.front();
            for(auto& x : graph[s]){
                if(dist[i][x] > dist[i][s] + 1) {
                    dist[i][x] = dist[i][s] + 1;
                    path[i][x] = path[i][s];

                    v[x] = 1;
                    q.push(x);
                } 
 
                else if(dist[i][x] == dist[i][s] + 1) path[i][x] += path[i][s];

                v[x] = 1;
            }
 
            q.pop();
        }
    }
 
    ll k;
    cin >> k;
 
    for(ll i = 1; i <= k; i ++){
        ll u, v;
        cin >> u >> v;
 
        range.pb({u, v});
    }
 
    for(ll i = 0; i < n; i ++){
        for(auto& x : range){
            if(dist[i][x.fr] + dist[i][x.sc] > dist[x.fr][x.sc]) continue;
            else if(path[x.fr][x.sc]) e[i] += ld(path[i][x.fr] * path[i][x.sc]) / ld(path[x.fr][x.sc]);
            // cout << x.fr << " " << x.sc << " " << ld(dist[i][x.fr] * dist[i][x.sc]) / ld(dist[x.fr][x.sc]) << "\n";
        }
 
        if(e[i] > mx) mx = e[i], res = i;
        // cout << e[i] << " ";
        // cout << "\n";
    }
 
    cout << res;
}
 
 
signed main()
{
    // cin.tie(0)->sync_with_stdio(0);
 
    if(fopen("TOY.inp", "r")){
        freopen("TOY.inp", "r", stdin);
        freopen("TOY.out", "w", stdout);
    }
    
    // cout << 1; return 0;
 
    ll n = 1;
 
    // cin >> n;
 
    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen("TOY.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen("TOY.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: 0 / 36