Submission #1190610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190610		MateiKing80	Escape Route (JOI21_escape_route)	C++20	100 / 100	2383 ms	160596 KiB

escape_route

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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define fr first
#define sc second
const ll inf = 1e18;

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>> c(N, vector<ll>(N, S));
    vector<vector<ll>> l(N, vector<ll>(N, S));
    for (int i = 0; i < M; i ++)
    {
        c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];
        l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
    }
    for (int i = 0; i < N; i ++)
        c[i][i] = l[i][i] = 0;
    auto dijkstra = [&](int p, int s)
    {
        vector<ll> d(N, inf);
        vector<bool> used(N, false);
        d[s] = c[p][s];
        for (int turip = 0; turip < N; turip ++)
        {
            int u = -1;
            for (int i = 0; i < N; i ++)
                if (!used[i] && (u == -1 || d[i] < d[u]))
                    u = i;
            used[u] = true;
            for (int v = 0; v < N; v ++)
            {
                if (used[v] || c[u][v] >= S)
                    continue;
                ll dd = d[u] + l[u][v];
                if (d[u] % S + l[u][v] > c[u][v])
                    dd += S - d[u] % S;
                d[v] = min(d[v], dd);
            }
        }
        return d;
    };

    vector<vector<vector<ll>>> d(N, vector<vector<ll>> (N, vector<ll>(N, inf)));
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            if (c[i][j] < S)
                d[i][j] = dijkstra(i, j);

    vector<ll> res(Q, inf);
    for (int i = 0; i < Q; i ++)
        res[i]= d[U[i]][U[i]][V[i]] + (S - T[i]) % S;

    for (int st = 0; st < N; st ++)
    {
        vector<pair<ll,int>> qq;
        for (int i = 0; i < Q; i ++)
            if(U[i] == st)
                qq.push_back({T[i], i});
        sort(qq.begin(), qq.end());
        vector<vector<pair<ll, int>>> ord(N);
        for (int i = 0; i < N; i ++)
        {
            for (int j = 0; j < N; j ++)
                if (i != j && c[i][j] < S)
                    ord[i].push_back({c[i][j] - l[i][j], j});
            sort(ord[i].rbegin(), ord[i].rend());
        }
        vector<int> pos(N, 0);
        vector<ll> dd(N, inf);
        dd[st] = 0;

        while (!qq.empty())
        {
            pair<ll, int> Max = {-1, -1};
            for (int i = 0; i < N; i ++)
                if (pos[i] < (int)ord[i].size())
                    Max = max(Max, {ord[i][pos[i]].fr - dd[i], i});
            while (!qq.empty() && qq.back().fr > Max.fr)
            {
                int id = qq.back().sc;
                qq.pop_back();
                res[id] = min(res[id], dd[V[id]]);
                for (int i = 0; i < N; i ++)
                {
                    if (dd[i] == inf)
                        continue;
                    res[id] = min(res[id], S - T[id] + d[i][i][V[id]]);
                }
            }
            if(Max.fr == -1)
                break;
            int u = Max.sc;
            int v = ord[u][pos[Max.sc] ++].sc;
            for (int i = 0; i < N; i ++)
                if(d[u][v][i] < S)
                    dd[i] = min(dd[i], d[u][v][i] - Max.fr);
        }
    }

    return res;
}

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