Submission #243529

#	Time	Username	Problem	Language	Result	Execution time	Memory
243529		SamAnd	Hotspot (NOI17_hotspot)	C++17	100 / 100	919 ms	1376 KiB

hotspot

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 5003;

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

int dx[N], dy[N];

int qx[N], qy[N];

bool c[N];
void bfs(int x, int d[], int qq[])
{
    memset(c, false, sizeof c);
    queue<int> q;
    c[x] = true;
    d[x] = 0;
    qq[x] = 1;
    q.push(x);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            if (!c[h])
            {
                c[h] = true;
                d[h] = d[x] + 1;
                q.push(h);
            }
            else if (d[h] == d[x] - 1)
            {
                qq[x] += qq[h];
            }
        }
    }
}

double ans[N];

void solv()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int qq;
    scanf("%d", &qq);
    while (qq--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        memset(qx, 0, sizeof qx);
        memset(qy, 0, sizeof qy);
        bfs(x, dx, qx);
        bfs(y, dy, qy);
        for (int z = 0; z < n; ++z)
        {
            if (dx[z] + dy[z] == dx[y])
            {
                ans[z] += (qx[z] * qy[z]) / (double)(qx[y]);
            }
        }
    }
    double maxu = -1.0;
    int maxx;
    for (int x = 0; x < n; ++x)
    {
        if (ans[x] > maxu)
        {
            maxu = ans[x];
            maxx = x;
        }
    }
    printf("%d\n", maxx);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

hotspot.cpp: In function 'void bfs(int, int*, int*)':
hotspot.cpp:33:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
hotspot.cpp: In function 'void solv()':
hotspot.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
hotspot.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
hotspot.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &qq);
     ~~~~~^~~~~~~~~~~
hotspot.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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