oj.uz

Submission #1105457

# Submission time Handle Problem Language Result Execution time Memory
1105457 2024-10-26T12:55:22 Z hainam2k9 Hotspot (NOI17_hotspot) C++17
100 / 100
 912 ms 197448 KB 
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "TRAINCENTRE";
int n,m,k,x,y;
vector<int> adj[5005];
pair<int,int> dist[5005][5005],p[2005];
pair<int,db> rs;
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n >> m;
    for(int i = 1; i<=m; ++i)
        cin >> x >> y, ++x, ++y, adj[x].pb(y), adj[y].pb(x);
    memset(dist,0x3f,sizeof(dist));
    for(int i = 1; i<=n; ++i){
        queue<int> q;
        q.push(i), dist[i][i].fi=0, dist[i][i].se=1;
        while(!q.empty()){
            int u = q.front();
            for(int v : adj[u]){
                if(dist[i][v].fi>dist[i][u].fi+1) dist[i][v].fi=dist[i][u].fi+1, dist[i][v].se=dist[i][u].se, q.push(v);
                else if(dist[i][v].fi==dist[i][u].fi+1) dist[i][v].se+=dist[i][u].se;
            }
            q.pop();
        }
    }
    cin >> k;
    for(int i = 1; i<=k; ++i)
        cin >> p[i].fi >> p[i].se, ++p[i].fi, ++p[i].se;
    for(int i = 1; i<=n; ++i){
        db e=0;
        for(int j = 1; j<=k; ++j){
            if(dist[i][p[j].fi].fi+dist[i][p[j].se].fi>dist[p[j].fi][p[j].se].fi) continue;
            e+=1.0L*dist[p[j].fi][i].se*dist[p[j].se][i].se/dist[p[j].fi][p[j].se].se;
        }
        if(e>rs.se) rs.fi=i, rs.se=e;
    }
    cout << rs.fi-1;
}

Compilation message

hotspot.cpp: In function 'int main()':
hotspot.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:28:45: note: in expansion of macro 'fo'
   28 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
hotspot.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:28:45: note: in expansion of macro 'fo'
   28 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 196424 KB Output is correct
2 Correct 32 ms 196688 KB Output is correct
3 Correct 32 ms 196856 KB Output is correct
4 Correct 27 ms 196600 KB Output is correct
5 Correct 28 ms 196444 KB Output is correct
6 Correct 26 ms 196432 KB Output is correct
7 Correct 31 ms 196684 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 196424 KB Output is correct
2 Correct 32 ms 196688 KB Output is correct
3 Correct 32 ms 196856 KB Output is correct
4 Correct 27 ms 196600 KB Output is correct
5 Correct 28 ms 196444 KB Output is correct
6 Correct 26 ms 196432 KB Output is correct
7 Correct 31 ms 196684 KB Output is correct
8 Correct 27 ms 196432 KB Output is correct
9 Correct 29 ms 196688 KB Output is correct
10 Correct 32 ms 196688 KB Output is correct
11 Correct 31 ms 196540 KB Output is correct
12 Correct 28 ms 196444 KB Output is correct
13 Correct 28 ms 196432 KB Output is correct
14 Correct 31 ms 196700 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 196424 KB Output is correct
2 Correct 32 ms 196688 KB Output is correct
3 Correct 32 ms 196856 KB Output is correct
4 Correct 27 ms 196600 KB Output is correct
5 Correct 28 ms 196444 KB Output is correct
6 Correct 26 ms 196432 KB Output is correct
7 Correct 31 ms 196684 KB Output is correct
8 Correct 29 ms 196432 KB Output is correct
9 Correct 31 ms 196648 KB Output is correct
10 Correct 31 ms 196432 KB Output is correct
11 Correct 34 ms 196660 KB Output is correct
12 Correct 24 ms 196424 KB Output is correct
13 Correct 26 ms 196424 KB Output is correct
14 Correct 28 ms 196432 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 196424 KB Output is correct
2 Correct 32 ms 196688 KB Output is correct
3 Correct 32 ms 196856 KB Output is correct
4 Correct 27 ms 196600 KB Output is correct
5 Correct 28 ms 196444 KB Output is correct
6 Correct 26 ms 196432 KB Output is correct
7 Correct 31 ms 196684 KB Output is correct
8 Correct 27 ms 196432 KB Output is correct
9 Correct 29 ms 196688 KB Output is correct
10 Correct 32 ms 196688 KB Output is correct
11 Correct 31 ms 196540 KB Output is correct
12 Correct 28 ms 196444 KB Output is correct
13 Correct 28 ms 196432 KB Output is correct
14 Correct 31 ms 196700 KB Output is correct
15 Correct 29 ms 196432 KB Output is correct
16 Correct 31 ms 196648 KB Output is correct
17 Correct 31 ms 196432 KB Output is correct
18 Correct 34 ms 196660 KB Output is correct
19 Correct 24 ms 196424 KB Output is correct
20 Correct 26 ms 196424 KB Output is correct
21 Correct 28 ms 196432 KB Output is correct
22 Correct 29 ms 196688 KB Output is correct
23 Correct 30 ms 196584 KB Output is correct
24 Correct 31 ms 196688 KB Output is correct
25 Correct 35 ms 196612 KB Output is correct
26 Correct 35 ms 196464 KB Output is correct
27 Correct 27 ms 196432 KB Output is correct
28 Correct 28 ms 196688 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 196424 KB Output is correct
2 Correct 32 ms 196688 KB Output is correct
3 Correct 32 ms 196856 KB Output is correct
4 Correct 27 ms 196600 KB Output is correct
5 Correct 28 ms 196444 KB Output is correct
6 Correct 26 ms 196432 KB Output is correct
7 Correct 31 ms 196684 KB Output is correct
8 Correct 27 ms 196432 KB Output is correct
9 Correct 29 ms 196688 KB Output is correct
10 Correct 32 ms 196688 KB Output is correct
11 Correct 31 ms 196540 KB Output is correct
12 Correct 28 ms 196444 KB Output is correct
13 Correct 28 ms 196432 KB Output is correct
14 Correct 31 ms 196700 KB Output is correct
15 Correct 33 ms 196688 KB Output is correct
16 Correct 34 ms 196688 KB Output is correct
17 Correct 70 ms 196680 KB Output is correct
18 Correct 46 ms 196688 KB Output is correct
19 Correct 76 ms 196680 KB Output is correct
20 Correct 32 ms 196544 KB Output is correct
21 Correct 27 ms 196680 KB Output is correct

Subtask #6
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 196424 KB Output is correct
2 Correct 32 ms 196688 KB Output is correct
3 Correct 32 ms 196856 KB Output is correct
4 Correct 27 ms 196600 KB Output is correct
5 Correct 28 ms 196444 KB Output is correct
6 Correct 26 ms 196432 KB Output is correct
7 Correct 31 ms 196684 KB Output is correct
8 Correct 27 ms 196432 KB Output is correct
9 Correct 29 ms 196688 KB Output is correct
10 Correct 32 ms 196688 KB Output is correct
11 Correct 31 ms 196540 KB Output is correct
12 Correct 28 ms 196444 KB Output is correct
13 Correct 28 ms 196432 KB Output is correct
14 Correct 31 ms 196700 KB Output is correct
15 Correct 29 ms 196432 KB Output is correct
16 Correct 31 ms 196648 KB Output is correct
17 Correct 31 ms 196432 KB Output is correct
18 Correct 34 ms 196660 KB Output is correct
19 Correct 24 ms 196424 KB Output is correct
20 Correct 26 ms 196424 KB Output is correct
21 Correct 28 ms 196432 KB Output is correct
22 Correct 29 ms 196688 KB Output is correct
23 Correct 30 ms 196584 KB Output is correct
24 Correct 31 ms 196688 KB Output is correct
25 Correct 35 ms 196612 KB Output is correct
26 Correct 35 ms 196464 KB Output is correct
27 Correct 27 ms 196432 KB Output is correct
28 Correct 28 ms 196688 KB Output is correct
29 Correct 33 ms 196688 KB Output is correct
30 Correct 34 ms 196688 KB Output is correct
31 Correct 70 ms 196680 KB Output is correct
32 Correct 46 ms 196688 KB Output is correct
33 Correct 76 ms 196680 KB Output is correct
34 Correct 32 ms 196544 KB Output is correct
35 Correct 27 ms 196680 KB Output is correct
36 Correct 58 ms 196856 KB Output is correct
37 Correct 116 ms 196948 KB Output is correct
38 Correct 864 ms 197192 KB Output is correct
39 Correct 104 ms 197192 KB Output is correct
40 Correct 370 ms 196872 KB Output is correct
41 Correct 912 ms 197448 KB Output is correct
42 Correct 227 ms 197192 KB Output is correct
43 Correct 144 ms 196680 KB Output is correct
44 Correct 145 ms 196688 KB Output is correct