oj.uz

답안 #1102916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102916 2024-10-19T08:43:22 Z Cam Hotspot (NOI17_hotspot) C++17
0 / 100
 8 ms 9296 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9296 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9296 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9296 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9296 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9296 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9296 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -