Submission #1105394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105394		TVSown	Hotspot (NOI17_hotspot)	C++17	100 / 100	622 ms	49340 KiB

hotspot

///*** Sown_Vipro ***///
/// ->GIAI BA QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, m, k;
vector<int> e[N];
vector<long long> dA(N), dB(N);
vector<int> cA(N), cB(N);
double ans[N];

void bfs(int s, vector<long long> &d, vector<int> &c){
    FOR(u, 0, n - 1){
        d[u] = 1e18;
        c[u] = 0;
    }
    d[s] = 0;
    c[s] = 1;
    queue<int> q;
    q.push(s);

    while(szz(q)){
        int u = q.front(); q.pop();
        for(int v : e[u]){
            if(d[u] + 1 < d[v]){
                d[v] = d[u] + 1;
                c[v] = c[u];
                q.push(v);
            }else if(d[u] + 1 == d[v]){
                c[v] += c[u];
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    FOR(i, 1, m){
        int u, v; cin >> u >> v;
        e[u].pb(v);
        e[v].pb(u);
    }
    cin >> k;
    FOR(i, 1, k){

        int a, b; cin >> a >> b;
        bfs(a, dA, cA);
        bfs(b, dB, cB);
//        cout << a << " " << b << " " << cA[b] << "\n";
        FOR(u, 0, n - 1){
            if(dA[u] + dB[u] == dA[b]){
//                cout << u << " " << a << " " << b << " " << cA[u] << " " << cB[u] << "\n";
                long double c = cA[u] * cB[u];
                ans[u] += c / cA[b];
            }
        }
    }

    long double r1 = 0;
    int r2 = 0;
    FOR(u, 0, n - 1){
//        cout << u << " " << ans[u] << "\n";
        if(ans[u] > r1){
            r1 = ans[u];
            r2 = u;
        }
    }

    cout << r2;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inp("in.txt");
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:16:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
hotspot.cpp:89:5: note: in expansion of macro 'inp'
   89 |     inp("in.txt");
      |     ^~~

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