Submission #723931

#	Time	Username	Problem	Language	Result	Execution time	Memory
723931		piOOE	Escape Route (JOI21_escape_route)	C++17	100 / 100	2638 ms	195508 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
                                    vector<int> U, vector<int> V, vector<ll> T) {
    constexpr ll inf = 3e18;
    vector<ll> answer(q, inf);
    vector<vector<int>> queries(n);

    for (int i = 0; i < q; ++i) {
        queries[U[i]].push_back(i);
    }

    A.resize(2 * m), B.resize(2 * m), L.resize(2 * m), C.resize(2 * m);
    for (int i = 0; i < m; ++i) {
        A[i + m] = B[i], B[i + m] = A[i];
        C[i + m] = C[i], L[i + m] = L[i];
    }
    m *= 2;

    vector<vector<int>> adj(n);

    for (int i = 0; i < m; ++i) {
        adj[A[i]].push_back(i);
    }

    auto dijkstra = [&](int source, ll s) -> vector<ll> {
        vector<ll> dist(n, inf);
        dist[source] = s;
        vector<bool> used(n);

        for (int _ = 0; _ < n; ++_) {
            int v = -1;
            for (int i = 0; i < n; ++i) {
                if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                    v = i;
                }
            }

            used[v] = true;

            for (int i : adj[v]) {
                int to = B[i];
                ll d = L[i] + (dist[v] % S <= C[i] - L[i] ? dist[v] : (dist[v] / S + 1) * S);
                if (dist[to] > d) {
                    dist[to] = d;
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            dist[i] = dist[i] - s;
        }

        return dist;
    };

    vector dist0(n, vector<ll>(n));
    vector dp(m, vector<ll>(n));

    for (int i = 0; i < n; ++i) {
        dist0[i] = dijkstra(i, 0);
    }

    for (int e = 0; e < m; ++e) {
        dp[e] = dijkstra(A[e], C[e] - L[e]);

        for (int to = 0; to < n; ++to) {
            if (C[e] - L[e] + dp[e][to] >= S) {
                dp[e][to] = inf;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        sort(adj[i].begin(), adj[i].end(), [&](int x, int y) {
            return C[x] - L[x] > C[y] - L[y];
        });
    };

    for (int i = 0; i < n; ++i) {
        sort(queries[i].begin(), queries[i].end(), [&](int x, int y) {
            return T[x] > T[y];
        });
        int k = 0;

        vector<int> id(n);
        vector<ll> d(m, inf);
        d[i] = 0;

        while (true) {
            pair<ll, int> best{-1, -1};

            for (int x = 0; x < n; ++x) {
                if (id[x] < adj[x].size()) {
                    int e = adj[x][id[x]];
                    best = max(best, {C[e] - L[e] - d[x], x});
                }
            }

            while (k < queries[i].size() && T[queries[i][k]] > best.first) {
                int j = queries[i][k++];
                answer[j] = min(answer[j], d[V[j]]);
                for (int x = 0; x < n; ++x) {
                    if (T[j] + d[x] < S) {
                        answer[j] = min(answer[j], S - T[j] + dist0[x][V[j]]);
                    }
                }
            }

            if (best.first == -1) {
                break;
            }

            int x = best.second;
            int e = adj[x][id[x]++];

            for (int to = 0; to < n; ++to) {
                d[to] = min(d[to], d[x] + dp[e][to]);
            }
        }
    }

    return answer;
}

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, ll, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:98:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 if (id[x] < adj[x].size()) {
escape_route.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while (k < queries[i].size() && T[queries[i][k]] > best.first) {
      |                    ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 30 / 30