Submission #935659

#	Time	Username	Problem	Language	Result	Execution time	Memory
935659		Pannda	Escape Route (JOI21_escape_route)	C++17	0 / 100	9093 ms	749496 KiB

escape_route

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30