oj.uz

Submission #790153

# Submission time Handle Problem Language Result Execution time Memory
790153 2023-07-22T11:13:57 Z VMaksimoski008 Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 14268 KB 
#include <bits/stdc++.h>
 
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
#define each(x, v) for(auto &x : v)
#define mp make_pair
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Node = array<ll, 3>;
 
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
 
void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int32_t main() {
    setIO();
 
    int n, m;
    cin >> n >> m;
    vector<vector<pii> > graph(n+1);
    int mat[n+1][n+1];
    memset(mat, 0, sizeof(mat));
    for(int i=0; i<m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        if(mat[a][b] == 0) mat[a][b] = w;
        else mat[a][b] = min(mat[a][b], w);
        graph[a].pb({ b, w });
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(mat[i][j] != 0)
                graph[i].pb({ j, mat[i][j] });
 
    int k, q;
    cin >> k >> q;
    k = min(k, n);
    vector<vector<ll> > ans(n+1, vector<ll>(n+1, 1e18));
    vector<vector<vector<ll> > > dist(n+1, vector<vector<ll>>(n+1, vector<ll>(k+1, 1e18)));
    priority_queue<Node, vector<Node>, greater<Node> > pq;

    for(int i=1; i<=n; i++) {
        dist[i][i][0] = 0;
        vector<vector<bool> > vis(n+1, vector<bool>(k+1, false));
        pq.push({ 0, 0, i });

        while(!pq.empty()) {
            ll d = pq.top().at(0);
            int c = pq.top().at(1);
            int u = pq.top().at(2);
            pq.pop();

            if(vis[u][c]) continue;
            vis[u][c] = true;

            if(c == k) continue;
            for(pii &v : graph[u]) {
                if(dist[i][v.first][c+1] > dist[i][u][c] + v.second) {
                    dist[i][v.first][c+1] = dist[i][u][c] + v.second;
                    pq.push({ dist[i][v.first][c+1], c+1, v.first });
                }
            }
        }

        for(int j=1; j<=n; j++) {
            for(int x=0; x<k+1; x++) {
                ans[i][j] = min(ans[i][j], dist[i][j][x]);
            }
        }
    }

    
    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << (ans[a][b] == 1e18 ? -1 : ans[a][b]) << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:66:16: warning: unused variable 'd' [-Wunused-variable]
   66 |             ll d = pq.top().at(0);
      |                ^

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 3 ms 712 KB Output is correct
4 Correct 3 ms 740 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 7 ms 816 KB Output is correct
7 Correct 8 ms 964 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 32 ms 1668 KB Output is correct
8 Correct 86 ms 3616 KB Output is correct
9 Correct 6 ms 852 KB Output is correct
10 Correct 72 ms 2224 KB Output is correct
11 Correct 34 ms 1260 KB Output is correct
12 Correct 175 ms 2924 KB Output is correct
13 Correct 279 ms 11408 KB Output is correct
14 Correct 435 ms 11524 KB Output is correct
15 Execution timed out 1082 ms 14268 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 3 ms 712 KB Output is correct
10 Correct 3 ms 740 KB Output is correct
11 Correct 4 ms 848 KB Output is correct
12 Correct 7 ms 816 KB Output is correct
13 Correct 8 ms 964 KB Output is correct
14 Correct 32 ms 1668 KB Output is correct
15 Correct 86 ms 3616 KB Output is correct
16 Correct 6 ms 852 KB Output is correct
17 Correct 72 ms 2224 KB Output is correct
18 Correct 34 ms 1260 KB Output is correct
19 Correct 175 ms 2924 KB Output is correct
20 Correct 279 ms 11408 KB Output is correct
21 Correct 435 ms 11524 KB Output is correct
22 Execution timed out 1082 ms 14268 KB Time limit exceeded
23 Halted 0 ms 0 KB -