Submission #1105401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105401		HNa_seawjing	Hotspot (NOI17_hotspot)	C++14	100 / 100	1258 ms	363004 KiB

hotspot

#include <bits/stdc++.h>
//code
#define fl(i,x,y,z) for(int i=x;i<=y;i=i+z)
#define fn(i,x,y,z) for(int i=x;i>=y;i=i-z)
#define rep(i,x,y) for(int i=x;i<y;i=i+1)
#define all(v) v.begin(),v.end()
#define pb emplace_back
#define tle cout<<"tle"<<endl
#define edl cout<<"\n"
#define el "\n"
#define getbit(x,i) ((x>>i)&1)
#define bitcnt __builtin_popcount
//ham
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
//#define int long long
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int maxn=1e6+5;
int n,m,k,d[5001][5001],ans_node,x[2001],y[2001];
vector<int> adj[5001];
queue<int> q;
long double ans,cnt[5001][5001];

void bfs(int x)
{
    memset(d[x],0x3f,sizeof(d[x]));
    q.push(x);
    d[x][x]=0;
    cnt[x][x]=1;

    while (!q.empty())
    {
        int a=q.front();
        q.pop();
        for (auto s : adj[a])
        {
            if (d[x][s]>d[x][a]+1)
            {
                d[x][s]=d[x][a]+1;
                cnt[x][s]+=cnt[x][a];
                q.push(s);
            }
            else if (d[x][s]==d[x][a]+1) cnt[x][s]+=cnt[x][a];
        }
    }
}
void inp()
{
    cin>>n>>m;
    for (int i=0; i<m; ++i)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin>>k;
    for (int i=0; i<k; ++i) cin>>x[i]>>y[i];
}
void sol()
{
    for (int i=0; i<n; ++i) bfs(i);
    for (int i=0; i<n; ++i)
    {
        long double sum=0;
        for (int j=0; j<k; ++j)
        {
            if (d[x[j]][i]+d[i][y[j]]==d[x[j]][y[j]])
                sum+=(cnt[x[j]][i]*cnt[i][y[j]])/cnt[x[j]][y[j]];
        }
        if (sum>ans) ans_node=i,ans=sum;
    }
    cout<<ans_node;
}
signed main()
{
#define name "seaw"
    if (fopen(name".inp", "r"))
    {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inp();
    sol();
    return 0;
}
/*   /\_/\
    ( ._. )
    / >V< \
*/

Compilation message (stderr)

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