Submission #1105391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105391		whoknow	Hotspot (NOI17_hotspot)	C++17	100 / 100	685 ms	1604 KiB

hotspot

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define F first
#define S second
#define MAXN 5005
#define MAXEDGE 40005
#define ii pair<ll,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, m, k;
vector<int>g[MAXN];
namespace sub1
{
double dp[MAXN];
ii d[MAXN][2];
bool visited[MAXN];
void bfs(int st, int j)
{
    for(int i = 0; i <= n; i++)
    {
        visited[i] = 0;
        d[i][j] = {1e18, 0};
    }
    queue<int>q;
    q.push(st);
    d[st][j] = {0, 1};
    while(q.empty() != 1)
    {
        int u = q.front();
        q.pop();
        if(visited[u])
            continue;
        visited[u] = 1;
        for(int v : g[u])
        {
            if(d[v][j].F > d[u][j].F + 1)
            {
                d[v][j] = {d[u][j].F + 1, d[u][j].S};
                q.push(v);
            }
            else if(d[v][j].F == d[u][j].F + 1)
                d[v][j].S += d[u][j].S;
        }
    }
}
void calc(int st, int ed)
{
    for(int i = 0; i < n; i++)
    {
        if(d[i][0].F + d[i][1].F == d[ed][0].F)
        {
            double t = 1.0 * d[i][0].S * d[i][1].S, t1 = max(d[st][1].S, d[ed][0].S);
            double x=1.0*t/t1;
            dp[i] += x;
        }
//        cout << setprecision(3) << fixed << dp[i] << endl;
    }
}
void solve()
{
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        bfs(x, 0);
        bfs(y, 1);
//        cout << i << ": ";
        calc(x, y);
    }
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        if(dp[i] > dp[res])
            res = i;
    }
    cout << res;
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    sub1::solve();
}
/**
4 6
0 1
1 2
2 3
3 0
0 2
3 1
3
0 2
3 2
1 2

**/

Compilation message (stderr)

hotspot.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main()
      | ^~~~
hotspot.cpp: In function 'int main()':
hotspot.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("TEST.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