oj.uz

Submission #935659

# Submission time Handle Problem Language Result Execution time Memory
935659 2024-02-29T10:37:55 Z Pannda Escape Route (JOI21_escape_route) C++17
0 / 100
 9000 ms 749496 KB 
#include "escape_route.h"

#include <bits/stdc++.h>
using namespace std;

vector<long long> calculate_necessary_time(int n, int m, long long S, int q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) {
    const long long INF = 9e18;

    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u = A[i];
        int v = B[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    vector<long long> res(q);
    for (int i = 0; i < q; i++) {
        map<pair<int, long long>, long long> dist;
        priority_queue<pair<long long, pair<int, long long>>, vector<pair<long long, pair<int, long long>>>, greater<>> pq;
        pq.push({dist[{U[i], T[i]}] = 0, make_pair(U[i], T[i])});
        while (!pq.empty()) {
            auto [d, ut] = pq.top();
            pq.pop();
            if (d != dist[ut]) continue;
            auto [u, t] = ut;
            for (auto [v, i] : adj[u]) {
                if (t <= C[i] - L[i]) {
                    long long tt = t + L[i];
                    if (!dist.count({v, tt}) || dist[{v, tt}] > d + L[i]) {
                        pq.push({dist[{v, tt}] = d + L[i], make_pair(v, tt)});
                    }
                }
            }
            long long tt = 0;
            if (!dist.count({u, tt}) || dist[{u, tt}] > d + S - t) {
                pq.push({dist[{u, tt}] = d + S - t, make_pair(u, tt)});
            }
        }
        long long mn = INF;
        for (auto [ut, d] : dist) {
            if (ut.first == V[i]) {
                mn = min(mn, d);
            }
        }
        res[i] = mn;
    }

    return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9039 ms 636384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9093 ms 749496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9039 ms 636384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9039 ms 636384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9039 ms 636384 KB Time limit exceeded
2 Halted 0 ms 0 KB -