제출 #1338874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338874		luvwinter	Hotspot (NOI17_hotspot)	C++20	38 / 100	6 ms	580 KiB

hotspot

#include<bits/stdc++.h>

#define boost() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define int long long
#define dd long double
#define pii pair<int , int>
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define in insert
#define lb lower_bound
#define ub upper_bound
#define FOR(i , l , r) for(int i = (l) ; i <= (r) ; i ++)
#define FOD(i , r , l) for(int i = (r) ; i >= (l) ; i --)
#define endl '\n'
#define all(x) x.begin() , x.end()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp make_pair

using namespace std;

const string NAME = "";
const int N = 5005;
const int INF = 1e18;

int n , m , k;
vector<int> adj[N];
int minto[N];
int cntmin[N];
int sum[N];
int gg[N];
int vv[N];
int zz[N];
pii road[N];

dd s[N];

int bfs(int a , int b) {
    queue<int> q;
    q.push(a);
    FOR(i , 1 , n) {
        minto[i] = INF;
        cntmin[i] = 0;
    }
    minto[a] = 0;
    cntmin[a] = 1;
    while(q.size()) {
        int u = q.front();
        q.pop();
        for(auto v : adj[u]) {
            if(minto[v] > minto[u] + 1) {
                minto[v] = minto[u] + 1;
                cntmin[v] = cntmin[u];
                q.push(v);
            }
            else if(minto[v] == minto[u] + 1) {
                cntmin[v] += cntmin[u];
                q.push(v);
            }

        }

    }
    return cntmin[b];
}



void solve () {
     cin >> n >> m;
     FOR(i , 1 , m) {
         int u , v; cin >> u >> v;
         u++; v++;
         adj[u].pb(v);
         adj[v].pb(u);
     }
     cin >> k;
     FOR(i , 1 , k) {
         cin >> road[i].fi >> road[i].se;
         road[i].fi++; road[i].se++;
         sum[i] = bfs(road[i].fi , road[i].se);
         gg[i] = minto[road[i].se];
         FOR(j , 1 , n) {
             vv[j] = cntmin[j];
             zz[j]= minto[j];
         }
         bfs(road[i].se , road[i].fi);
         FOR(j , 1 , n) {

              if(zz[j] + minto[j] == gg[i]) s[j] += (vv[j] * cntmin[j]) * 1.0 / sum[i];
             // cout << vv[j] << " " << cntmin[j] << " " << j <<  " " << i << " " << sum[i] << endl;
         }
     }
     //FOR(i , 1 , n) cout << s[i] << " " << i << endl;
     int ans = -1 ; dd p = 0;
     FOR(i , 1 , n) {
         if(s[i] > p) {
            p = s[i];
            ans = i;
         }
     }
     cout << ans - 1;





}

main () {
   boost();
   if(fopen((NAME + ".INP").c_str(), "r")) fo;
   solve();

   return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

hotspot.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main () {
      | ^~~~
hotspot.cpp: In function 'int main()':
hotspot.cpp:4:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:116:44: note: in expansion of macro 'fo'
  116 |    if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                            ^~
hotspot.cpp:4:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:116:44: note: in expansion of macro 'fo'
  116 |    if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                            ^~

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