Submission #521992

#	Time	Username	Problem	Language	Result	Execution time	Memory
521992		eecs	Escape Route (JOI21_escape_route)	C++17	100 / 100	4536 ms	144592 KiB

escape_route

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

typedef long long ll;
const ll INF = 1e18;

void chk(ll &x, ll y) {
    if (x > y) x = y;
}

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) {
    vector<vector<ll>> W(n, vector<ll>(n, -1)), lim = W;
    for (int i = 0; i < m; i++) {
        W[A[i]][B[i]] = W[B[i]][A[i]] = L[i];
        lim[A[i]][B[i]] = lim[B[i]][A[i]] = C[i] - L[i];
    }
    auto dijkstra = [&](vector<ll> &d) {
        vector<bool> vis(n);
        while (1) {
            int u = -1;
            for (int i = 0; i < n; i++) {
                if (!vis[i] && d[i] < INF && (!~u || d[u] > d[i])) u = i;
            }
            if (!~u) break;
            vis[u] = 1;
            for (int i = 0; i < n; i++) if (~W[u][i]) {
                if (d[u] % S <= lim[u][i]) chk(d[i], d[u] + W[u][i]);
                else chk(d[i], (d[u] + S - 1) / S * S + W[u][i]);
            }
        }
    };
    vector<vector<ll>> dv(n, vector<ll>(n, INF));
    vector<vector<vector<ll>>> de(n, dv);
    for (int i = 0; i < n; i++) {
        dv[i][i] = 0, dijkstra(dv[i]);
        for (int j = 0; j < n; j++) if (~W[i][j]) {
            de[i][j][i] = lim[i][j], dijkstra(de[i][j]);
            for (int k = 0; k < n; k++) {
                de[i][j][k] = de[i][j][k] < S ? de[i][j][k] - lim[i][j] : INF;
            }
        }
    }
    vector<vector<int>> G(n), Q(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (~W[i][j]) G[i].push_back(j);
        }
        sort(G[i].begin(), G[i].end(), [&](int x, int y) { return lim[i][x] > lim[i][y]; });
    }
    vector<ll> ans(q, INF);
    for (int i = 0; i < q; i++) {
        Q[U[i]].push_back(i);
    }
    for (int s = 0; s < n; s++) {
        sort(Q[s].begin(), Q[s].end(), [&](int x, int y) { return T[x] < T[y]; });
        vector<int> cur(n);
        vector<ll> dist(n, INF), tim(n, -1);
        dist[s] = 0, tim[s] = lim[s][G[s][0]];
        while (1) {
            int u = max_element(tim.begin(), tim.end()) - tim.begin();
            for (; !Q[s].empty() && T[Q[s].back()] > tim[u]; Q[s].pop_back()) {
                int k = Q[s].back();
                for (int i = 0; i < n; i++) {
                    chk(ans[k], dist[i] + (i != V[k] ? (S - (dist[i] + T[k]) % S) % S : 0) + dv[i][V[k]]);
                }
            }
            if (!~tim[u]) break;
            int v = G[u][cur[u]++];
            tim[u] = cur[u] < G[u].size() ? lim[u][G[u][cur[u]]] - dist[u] : -1;
            for (int i = 0; i < n; i++) if (dist[i] > dist[u] + de[u][v][i]) {
                dist[i] = dist[u] + de[u][v][i];
                if (cur[i] < G[i].size()) tim[i] = lim[i][G[i][cur[i]]] - dist[i];
            }
        }
    }
    return ans;
}

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:72:29: 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]
   72 |             tim[u] = cur[u] < G[u].size() ? lim[u][G[u][cur[u]]] - dist[u] : -1;
escape_route.cpp:75:28: 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]
   75 |                 if (cur[i] < G[i].size()) tim[i] = lim[i][G[i][cur[i]]] - dist[i];

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