oj.uz

Submission #698840

# Submission time Handle Problem Language Result Execution time Memory
698840 2023-02-14T12:13:45 Z Gital Autobus (COCI22_autobus) C++11
15 / 70
 1000 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
ll dp[75][75];
ll path[75][75];
//vector<pair<ll,ll>> v[75];
//bool checked[75];
int n,m;
//priority_queue<pair<pair<ll,ll>,set<int>>,vector<pair<pair<ll,ll>,set<int>>>,greater<pair<pair<ll,ll>,set<int>>>> pq;
int k,q;
int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        ll a,b,c; cin >> a >> b >> c;
        if(path[a][b] == 0 || path[a][b] > c) path[a][b] = c;
    }
    cin >> k >> q;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            dp[i][j] = -1;
        }
    }
    for(int i = 0; i < q; i++) {
        int c,d; cin >> c >> d;
        priority_queue<pair<pair<ll,ll>,set<int>>,vector<pair<pair<ll,ll>,set<int>>>,greater<pair<pair<ll,ll>,set<int>>>> pq;
        dp[c][c] = 0;
        if(dp[c][d] != -1) {
            cout << dp[c][d] << endl;
            continue;
        }
        set<int> s;
        pq.push({{0,c},s});
        while(!pq.empty()) {
            ll a = pq.top().first.first;
            ll b = pq.top().first.second;
            set<int> cnt = pq.top().second;
            pq.pop();
            cnt.insert(b);
            if(cnt.size() >= k + 1) continue;
            for(int j = 1; j <= n; j++) {
                if(path[b][j] != 0) {
                    if(dp[c][j] == -1) dp[c][j] = a + path[b][j];
                    else dp[c][j] = min(dp[c][j], a + path[b][j]);
                    if(!cnt.count(j))pq.push({{a + path[b][j],j},cnt});
                }
            }
        }
        cout << dp[c][d] << endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:41:27: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             if(cnt.size() >= k + 1) continue;
      |                ~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 380 KB Output is correct
2 Correct 39 ms 432 KB Output is correct
3 Correct 26 ms 484 KB Output is correct
4 Correct 23 ms 460 KB Output is correct
5 Correct 117 ms 824 KB Output is correct
6 Correct 60 ms 652 KB Output is correct
7 Execution timed out 1084 ms 10180 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Runtime error 984 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 380 KB Output is correct
8 Correct 39 ms 432 KB Output is correct
9 Correct 26 ms 484 KB Output is correct
10 Correct 23 ms 460 KB Output is correct
11 Correct 117 ms 824 KB Output is correct
12 Correct 60 ms 652 KB Output is correct
13 Execution timed out 1084 ms 10180 KB Time limit exceeded
14 Halted 0 ms 0 KB -