oj.uz

답안 #1112283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112283 2024-11-14T02:35:37 Z Zero_OP Construction Project 2 (JOI24_ho_t2) C++14
45 / 100
 2000 ms 20168 KB 
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;

void testcase(){
    int N, M, S, T, L; long long K;
    cin >> N >> M >> S >> T >> L >> K;

    --S, --T;
    vector<vector<pair<int, int>>> adj(N);
    while(M--){
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    auto dijkstra = [&](int s){
        vector<long long> d(N, inf);
        d[s] = 0;

        using node = pair<long long, int>;
        priority_queue<node, vector<node>, greater<node>> pq;
        pq.push({d[s], s});

        while(!pq.empty()){
            long long cur; int u;
            tie(cur, u) = pq.top(); pq.pop();
            for(auto [v, w] : adj[u]){
                if(d[v] > d[u] + w){
                    d[v] = d[u] + w;
                    pq.push({d[v], v});
                }
            }
        }
        return d;
    };

    vector<long long> dS = dijkstra(S), dT = dijkstra(T);

    if(dS[T] <= K){
        cout << 1LL * N * (N - 1) / 2;
        return;
    }

    int cnt = 0;
    for(int i = 0; i < N; ++i){
        for(int j = i + 1; j < N; ++j){
            long long cur = min(dS[i] + dT[j], dS[j] + dT[i]) + L;
            if(cur <= K) ++cnt;
        }
    }

    cout << cnt << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
//    cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:32:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |             for(auto [v, w] : adj[u]){
      |                      ^

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Execution timed out 2094 ms 20168 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 508 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 456 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 516 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 508 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 456 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 516 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 6 ms 592 KB Output is correct
34 Correct 2 ms 592 KB Output is correct
35 Correct 6 ms 472 KB Output is correct
36 Correct 9 ms 764 KB Output is correct
37 Correct 6 ms 468 KB Output is correct
38 Correct 6 ms 592 KB Output is correct
39 Correct 7 ms 592 KB Output is correct
40 Correct 2 ms 836 KB Output is correct
41 Correct 1 ms 592 KB Output is correct
42 Correct 6 ms 592 KB Output is correct
43 Correct 7 ms 636 KB Output is correct
44 Correct 7 ms 592 KB Output is correct
45 Correct 6 ms 592 KB Output is correct
46 Correct 6 ms 592 KB Output is correct
47 Correct 6 ms 624 KB Output is correct
48 Correct 7 ms 592 KB Output is correct
49 Correct 2 ms 592 KB Output is correct
50 Correct 6 ms 592 KB Output is correct
51 Correct 7 ms 632 KB Output is correct
52 Correct 7 ms 776 KB Output is correct
53 Correct 7 ms 848 KB Output is correct
54 Correct 7 ms 876 KB Output is correct
55 Correct 5 ms 764 KB Output is correct
56 Correct 4 ms 592 KB Output is correct
57 Correct 4 ms 592 KB Output is correct
58 Correct 4 ms 592 KB Output is correct

Subtask #4
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Execution timed out 2094 ms 20168 KB Time limit exceeded
8 Halted 0 ms 0 KB -