제출 #707813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707813		LittleCube	Escape Route (JOI21_escape_route)	C++17	100 / 100	3158 ms	682312 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
using namespace std;

const ll inf = 100'000'000'000'000'000;
ll d1[90][90 * 90 + 5][90], d2[90][90], from[90];
vector<ll> tp[90];
vector<pll> last[90][90];

int getT(int i, ll t)
{
    return upper_bound(tp[i].begin(), tp[i].end(), t, greater<>()) - tp[i].begin() - 1;
}

void update(int N, int r, int t, int u, int v, ll w)
{
    int vt = getT(v, d1[r][t][u] + w);
    if (vt < 0)
        return;
    for (int i = 0; i < N; i++)
        d1[r][t][i] = min(d1[r][t][u] + w + d1[v][vt][i] - tp[v][vt], d1[r][t][i]);
}

pll calcNextEdge(int N, int r, ll T, int t)
{
    ll nt = -1, ni = -1, nj = -1;
    for (int i = 0; i < N; i++)
        if (!last[r][i].empty())
            if (nt < T - (d1[r][t][i] - last[r][i].back().F))
                nt = T - (d1[r][t][i] - last[r][i].back().F), ni = i;

    if (ni >= 0)
    {
        nj = last[r][ni].back().S;
        last[r][ni].pop_back();
    }
    return pll(nj, nt);
}

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)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            last[i][A[j]].emplace_back(pll(C[j] - L[j], j));
            last[i][B[j]].emplace_back(pll(C[j] - L[j], j));
        }
        for (int j = 0; j < N; j++)
            sort(last[i][j].begin(), last[i][j].end());
    }

    priority_queue<tuple<ll, int, int>> pq;
    for (int i = 0; i < N; i++)
    {
        tp[i].emplace_back(S - 1);
        for (int j = 0; j < N; j++)
            d1[i][0][j] = (i == j ? S - 1 : inf << 1);
        auto [j, nt] = calcNextEdge(N, i, tp[i].back(), (int)tp[i].size() - 1);
        if (nt >= 0)
            pq.push(make_tuple(nt, i, j));
    }

    while (!pq.empty())
    {
        auto [t, i, j] = pq.top();
        pq.pop();
        if (t < tp[i].back())
        {
            tp[i].emplace_back(t);
            int tt = (int)tp[i].size() - 1;
            for (int k = 0; k < N; k++)
                d1[i][tt][k] = d1[i][tt - 1][k] - (tp[i][tt - 1] - tp[i][tt]);
        }
        update(N, i, (int)tp[i].size() - 1, A[j], B[j], L[j]);
        update(N, i, (int)tp[i].size() - 1, B[j], A[j], L[j]);
        auto [k, nt] = calcNextEdge(N, i, tp[i].back(), (int)tp[i].size() - 1);
        if (nt >= 0)
            pq.push(make_tuple(nt, i, k));
    }

    // for (int i = 0; i < N; i++)
    //     for (int j = 0; j < tp[i].size(); j++)
    //     {
    //         cerr << i << " (time " << tp[i][j] << ") ";
    //         for (int k = 0; k < N; k++)
    //             cout << d1[i][j][k] << " \n"[k == N - 1];
    //     }

    vector<pair<int, pll>> E[90];
    for (int i = 0; i < M; i++)
    {
        E[A[i]].emplace_back(make_pair(B[i], pll(C[i], L[i])));
        E[B[i]].emplace_back(make_pair(A[i], pll(C[i], L[i])));
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            d2[i][j] = (i == j ? 0 : inf);
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        pq.push(pll(0, i));
        while (!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > d2[i][u])
                continue;
            for (auto [v, p] : E[u])
            {
                auto [c, l] = p;
                ll nd = (d % S <= c - l ? d : (d + S - 1) / S * S) + l;
                if (nd < d2[i][v])
                {
                    d2[i][v] = nd;
                    pq.push(pll(d2[i][v], v));
                }
            }
        }
    }
    // for (int i = 0; i < N; i++)
    //     for (int j = 0; j < N; j++)
    //         cerr << d2[i][j] << " \n"[j == N - 1];
    vector<ll> ans(Q);
    for (int i = 0; i < Q; i++)
    {
        int t = upper_bound(tp[U[i]].begin(), tp[U[i]].end(), T[i], greater<>()) - tp[U[i]].begin() - 1;
        ans[i] = inf;
        for (int j = 0; j < N; j++)
            if (d1[U[i]][t][j] < inf)
            {
                if (j == V[i])
                    ans[i] = min(ans[i], d1[U[i]][t][j] - tp[U[i]][t]);
                else
                    ans[i] = min(ans[i], S + d2[j][V[i]] - T[i]);
            }
    }
    return ans;
}

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