Submission #1102916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102916		Cam	Hotspot (NOI17_hotspot)	C++17	0 / 100	8 ms	9296 KiB

hotspot

#include <bits/stdc++.h>
#define name "traincentre"
#define ll long long
#define db double
#define pb push_back
#define ii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define bit(x,i) (((x)>>(i))&1)
#define sz(s) (int)(s).size()
#define all(a) (a).begin(),(a).end()
#define rep(i,a,b) for(int i=(a), _b=(b); i<=_b; i++)
#define repd(i,a,b) for(int i=(a), _b=(b); i>=_b; i--)
#define _unique(x) (x).resize(unique(all(x)) - (x).begin())

using namespace std;

const int N = 1e5 + 3;
const int inf = 1e9 + 7;
const int base = 31;
const double eps = 0.00000001;

int n, m, k;
int d[2][N];
ll cnt[2][N], ans[N], res;
vector <int> a[N];

void dijkstra (int o, int s) {

    rep (i, 1, n) d[o][i] = inf, cnt[o][i] = 0;
    priority_queue <ii, vector <ii>, greater <ii> > q;
    q.push (mp (0, s)); d[o][s] = 0; cnt[o][s] = 1;

    while (sz (q)) {

        int u = q.top().se, du = q.top().fi; q.pop();
        if (du > d[o][u]) continue;
        for (int v : a[u]) {

            if (d[o][v] > d[o][u] + 1) {

                d[o][v] = d[o][u] + 1;
                q.push (mp (d[o][v], v));
                cnt[o][v] = cnt[o][u];
            }
            if (d[o][v] == d[o][u] + 1) cnt[o][v] += cnt[o][u];
        }
    }
}
void solve (void) {

    cin >> n >> m;
    rep (i, 1, m) {

        int u, v; cin >> u >> v;
        u ++; v ++;
        a[u].pb (v); a[v].pb (u);
    }
    cin >> k;
    rep (i, 1, k) {

        int x, y;
        cin >> x >> y;
        x ++; y ++;
        dijkstra (0, x); dijkstra (1, y);
        rep (u, 1, n) if (d[0][u] + d[1][u] == d[0][y]) {

            ans[u] += (cnt[0][u] * cnt[1][u]) / cnt[0][y];
        }
    }
    int u;
    rep (i, 1, n) if (ans[i] > res) {

        res = ans[i];
        u = i;
    }
    cout << u - 1;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(name".inp","r",stdin);
    //freopen(name".out","w",stdout);

    solve();
    return 0;
}

Compilation message (stderr)

hotspot.cpp: In function 'void solve()':
hotspot.cpp:78:17: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     cout << u - 1;
      |                 ^

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