Submission #1102950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102950		Cam	Hotspot (NOI17_hotspot)	C++17	100 / 100	621 ms	7932 KiB

hotspot

#include <bits/stdc++.h>
using namespace std;
 
#define task "TRAINCENTER"
#define fi first
#define se second
#define pii pair <int, int>
#define pb push_back
#define ll long long 
#define pip pair <int, pii>
#define pli pair <ll, int>
#define double long double
 
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
 
int myabs(int x)
{
    return x < 0 ? -x : x;
}
 
int n, m, k;
vector <int> g[N];
long long cnt[2][N], d[2][N];
double ans[N];
 
void inp()
{
    cin >> n >> m;
    for (int i=1; i<=m; ++i)
    {
        int u, v;
        cin >> u >> v;
        u++;
        v++;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> k;
}
 
void bfs(int id, int s)
{
    queue <int> q;
    for (int i=0; i<=n; ++i)
        d[id][i] = -1,
        cnt[id][i] = 0;
    d[id][s] = 0;
    q.push(s);
    cnt[id][s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : g[u])
        {
            if (d[id][v] == -1)
            {
                d[id][v] = d[id][u] + 1;
                cnt[id][v] = cnt[id][u];
                q.push(v);
            }
            else if (d[id][v] == d[id][u] + 1)
                cnt[id][v] += cnt[id][u];
        }
    }
}
 
void solve()
{
    while (k--)
    {
        int a, b;
        cin >> a >> b;
        a++;
        b++;
        bfs(0, a);
        bfs(1, b);
        double tmp = cnt[0][b];
        for (int i=1; i<=n; ++i)
            if (d[0][i] + d[1][i] == d[0][b])
            {
                double tmp1 = (double)(cnt[0][i] * cnt[1][i]);
                ans[i] += (tmp1/tmp);
            }
    }
    int res = 0;
    for (int i=1; i<=n; ++i)
        if (ans[i] > ans[res])
            res = i;
    cout << res - 1;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    inp();
    solve();
    return 0;
}

Compilation message (stderr)

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