oj.uz

Submission #705869

# Submission time Handle Problem Language Result Execution time Memory
705869 2023-03-05T14:37:40 Z Gital Autobus (COCI22_autobus) C++11
30 / 70
 1000 ms 18396 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;

ll n,m,a,b,w;
ll k,q,c,d;
vector<pair<ll,ll>> v[72];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
ll dp[72][72][72];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> w;
        v[a].push_back({w,b});
    }
    cin >> k >> q;
    if(k > 70) k = 70;
    for(int i = 0; i < 71; i++) {
        for(int j = 0; j < 71; j++) {
            for(int l= 0; l < 71; l++) dp[i][j][l] = -1;
        }
    }
    for(int j = 1; j <= n; j++) {
        pq.push({0,j});
        for(int i = 0; i < 72; i++) dp[j][j][i] = 0;
        while(!pq.empty()) {
            a = pq.top().first;
            b = pq.top().second;
            pq.pop();
            for(int i = 0; i < v[b].size(); i++) {
                bool able = false;
                for(int l = 0; l < k; l++) {
                    if(dp[j][b][l] != -1  && (dp[j][v[b][i].second][l + 1] == -1 || dp[j][v[b][i].second][l + 1] > dp[j][b][l] + v[b][i].first)) {
                        dp[j][v[b][i].second][l + 1] = dp[j][b][l] + v[b][i].first;
                        if(!able) pq.push({dp[j][v[b][i].second][l + 1],v[b][i].second});
                        able = true;
                    }
                }

            }
        }
    }
    /*for(int i = 1; i < 5; i++) {
        cout << "i = " << i << endl;
        for(int j = 1; j < 5; j++) {
            cout << "j = " << j << endl;
            for(int l= 0; l < 2; l++)  {
                cout << dp[i][j][l] << ' ';
            }
            cout << endl;
        }
    }*/
    for(int i = 0; i < q; i++) {
        cin >> c >> d;
        cout << dp[c][d][k] << endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int i = 0; i < v[b].size(); i++) {
      |                            ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3144 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3284 KB Output is correct
2 Correct 3 ms 3292 KB Output is correct
3 Correct 4 ms 3284 KB Output is correct
4 Correct 4 ms 3288 KB Output is correct
5 Correct 5 ms 3300 KB Output is correct
6 Correct 10 ms 3484 KB Output is correct
7 Correct 18 ms 3508 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3144 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 9 ms 3288 KB Output is correct
8 Correct 16 ms 3284 KB Output is correct
9 Correct 6 ms 3284 KB Output is correct
10 Correct 23 ms 3284 KB Output is correct
11 Correct 38 ms 3412 KB Output is correct
12 Correct 163 ms 3472 KB Output is correct
13 Execution timed out 1080 ms 18396 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3144 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3292 KB Output is correct
9 Correct 4 ms 3284 KB Output is correct
10 Correct 4 ms 3288 KB Output is correct
11 Correct 5 ms 3300 KB Output is correct
12 Correct 10 ms 3484 KB Output is correct
13 Correct 18 ms 3508 KB Output is correct
14 Correct 9 ms 3288 KB Output is correct
15 Correct 16 ms 3284 KB Output is correct
16 Correct 6 ms 3284 KB Output is correct
17 Correct 23 ms 3284 KB Output is correct
18 Correct 38 ms 3412 KB Output is correct
19 Correct 163 ms 3472 KB Output is correct
20 Execution timed out 1080 ms 18396 KB Time limit exceeded
21 Halted 0 ms 0 KB -